这么简单的算法之前写过思路,这次是复习一遍。
如果看思路:https://www.z88j.com/106.html (这个是php版本的 不过算法和语言没多大关系)
值得注意的是 c++ swap 实际性能并没有 普通的变量交换性能高。好像是因为泛型 要进行类型判断。
c++选择排序代码:
#include <iostream>
using namespace std;
/**
* 选择排序
* @param arr
* @param n
*/
void selectionSort(int arr[],int n){
for (int i = 0; i < n; ++i) {
//寻找[i,n]区间里的最小值
int minIndex = i;
for (int j = i+1; j < n; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
swap(arr[i],arr[minIndex]);
}
}
};
int main() {
std::cout << "Hello, World!" << std::endl;
int a[10] = {10,9,8,7,6,5,4,3,2,1};
selectionSort(a,10);
for (int i = 0; i < 10; ++i) {
cout << a[i] <<" ";
cout << endl;
}
return 0;
}
使用swap交换变量
template<typename T>
void bubbleSort2(T arr[], int n){
int newn; //使用newn进行优化
do{
newn = 0;
for(int i = 1; i < n; i ++){
if(arr[i-1] > arr[i]){
swap(arr[i-1], arr[i]);
// 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
newn = i;
}
}
n = newn;
}while(newn > 0);
}
使用基本交换
template<typename T>
void bubbleSort4(T arr[], int n){
int newn; //使用newn进行优化
int i,j;
T temp;
do{
newn = 0;
for(i = 1; i < n; i ++){
if(arr[i-1] > arr[i]){
temp = arr[i-1];
arr[i-1] = arr[i];
arr[i] = temp;
// 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
newn = i;
}
}
n = newn;
}while(newn > 0);
}
原创文章,作者:星辰,如若转载,请注明出处:https://www.z88j.com/290.html