「算法」排序算法基础（排序算法模板）

自动生成数组：

 int *generateRandomArray(int n, int rangeL, int rangeR) {
 assert(rangeL <= rangeR);
 int *arr = new int[n];
 srand(time(NULL));
 for (int i = 0; i < n; i++)
 arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
 return arr;
 }

测试时间：

 void testSort(const string sortName, void (*sort)(T[], int), T arr[], int n) {
 clock_t startTime = clock();
 sort(arr, n);
 clock_t endTime = clock();
 cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
 return;
 }

选择排序：

template<typename T>
void selectionSort(T 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] );
 }
}

插入排序：对近乎有序的数组排序效率最高。

//一种写法，每比较一次交换一次，时间上比选择排序更长
void insertionSort(T arr[], int n){
 for( int i = 1 ; i < n ; i ++ ) {
 // 每次起一张牌，
 for( int j = i ; j > 0 ; j-- )
 if( arr[j] < arr[j-1] )
 swap( arr[j] , arr[j-1] );
 }
 return;
}
//另一种写法，往后赋值，效率更高。
void insertionSort(T arr[], int n){
 for( int i = 1 ; i < n ; i ++ ) {
 T e = arr[i];
 int j; // j保存元素e应该插入的位置
 for (j = i; j > 0 && arr[j-1] > e; j--)
 arr[j] = arr[j-1];
 arr[j] = e;
 }
 return;
}

冒泡排序也是常见方法，奥巴马也会的。

希尔排序是插入排序的一种改进，加入了步长的概念。

可以参见干货菌其他文章：https://www.toutiao.com/i6600553503154766339/