冒泡排序是比較簡單的O(n2)級別的排序算法，思路是挨個比較鄰近的數(shù)值，然后交換位置，就像在水里的泡泡一樣，總能把最大的或者最小的交換到最上層。
/** * 冒泡排序 */template<typename T>void bubble_sort(T arr[], int length){ for (int i=0; i< length-1; i ){ for(int j=0; j< length-1-i; j ){ if (arr[j] > arr[j 1]){ swap(arr[j], arr[j 1]); } } }}選擇排序的算法級別也是O(n2)，思路是從第一個索引開始，與剩下的進(jìn)行比較，并記錄最下的值的索引，依次比較下去。如果當(dāng)前索引和初始的索引不同，那么需要交換值。此時最小的元素排在了前面。然后依次類推。
/** *選擇排序 */template<typename T>void select_sort(T arr[], int length){ for (int i=0; i<length-1; i ){ int minIndex = i; for(int j = i 1; j<length; j ){ if(arr[minIndex] > arr[j]){ minIndex = j; } } if(minIndex!=i){ swap(arr[i], arr[minIndex]); } }}插入排序，假設(shè)前面的數(shù)據(jù)是排列完整的，那么需要把當(dāng)前的值與它前面的依次比較，直到遇到大于的位置，然后插入到其中。一般實(shí)現(xiàn)的時候可以選擇依次交換位置，也可以進(jìn)行賦值。
具體實(shí)現(xiàn)如下：
/** * 插入排序 交換數(shù)值 */template <typename T>void insert_sort(T arr[], int length){ for(int i=0; i< length -1; i ){ for (int j = i 1; j>0 && (arr[j-1] > arr[j]); j--){ //if (arr[j-1] > arr[j]){ swap(arr[j-1], arr[j]); // } } }}可以對其進(jìn)行優(yōu)化，不需要每次都進(jìn)行交換鄰近，這樣勢必會浪費(fèi)空間和時間，可以賦值操作
template <typename T>void insert_sort2(T arr[], int length){ for(int i=1; i< length; i ){ T val = arr[i]; // 當(dāng)前元素的值 int j; for(j=i; j>0 && val < arr[j-1]; j--){ arr[j] = arr[j-1]; // 向前移動 } if(j!=i){ arr[j] = val; } }}從代碼中也可以看出，插入排序?qū)Υ蟛糠峙藕玫男蛄惺呛芸斓摹?/p>
插入排序是采用1步長進(jìn)行排序的，而希爾排序在插入排序的基礎(chǔ)上，先采用大步長，只到1步長為止，思想從整體上使得序列基本有序。
/** *希爾排序 * */template <typename T>void shell_sort(T arr[], int length){ int gap = 1; while (gap < length / 3) { gap = 3 * gap 1; } cout << "gap = " << gap << endl; // 間隔Gap 進(jìn)行插入排序 while (gap>0) { // 這里其實(shí)就是插入排序，只是以gap為間隔進(jìn)行排序 for(int i = 0; i <length; i = gap){ for(int j= i gap; j > 0 && (arr[j] < arr[j-gap]); j -= gap){ swap(arr[j], arr[j-gap]); } } gap = gap/3; }}就是不斷的把一個數(shù)組，對半分成兩份，只到最后不能再分，然后再向上進(jìn)行排序合并，典型的遞歸的思想
/** *歸并排序 * 分為左右，然后排序，然后合并 開辟臨時內(nèi)存空間 */template <typename T>void merge_sort(T arr[], int length){ __merge_sort(arr, 0, length-1);}template <typename T>void __merge_sort(T arr[], int l, int r){ if (l >=r){ return; } int mid = l (r-l) /2; //(r l)/2; __merge_sort(arr, l, mid); __merge_sort(arr, mid 1, r); // [l, mid] [mid 1, r] T * aux = new T[r-l 1]; for(int i=l; i<=r; i ){ aux[i-l] = arr[i]; } int i = l, j = mid 1; for(int k = l; k <= r; k ){ if (i > mid){ arr[k] = aux[j-l]; // 復(fù)制剩下的右半邊 j ; }else if (j > r){ arr[k] = aux[i-l]; // 復(fù)制剩下的左半邊 i ; }else if(aux[i-l] < aux[j-l]){ arr[k] = aux[i-l]; // 復(fù)制左半邊 i ; } else{ arr[k] = aux[j-l]; // 復(fù)制右半邊 j ; } } delete[] aux;}快速排序的思想也是分而治之，首選需要選擇一個基本值，然后小于基本值的在數(shù)組的左半邊，大于的在右半邊，中間部分是基本值，然后依次在對基本值的左邊遞歸，對右半邊也遞歸。
/** *快速排序 需要選擇基準(zhǔn)的數(shù)據(jù)，默認(rèn)第一個，也可以隨機(jī)選擇 */template<typename T>void quick_sort(T arr[], int length){ __quick_sort(arr, 0, length-1);}template<typename T>void __quick_sort(T arr[], int l, int r){ if(l >= r) { return; } int index = __partition(arr, l, r); __quick_sort(arr, l, index-1); __quick_sort(arr, index 1, r);}template <typename T>int __partition(T arr[], int l, int r){ // 從兩端向內(nèi) //int index = rand()%(r-l 1) l; //swap(arr[l], arr[index]); T v = arr[l]; // 選擇第一個為基準(zhǔn)值，也可隨機(jī)選擇，然后交換再進(jìn)行 int i = l 1, j = r; while( true ){ // 注意這里的邊界, arr[i] < v, 不能是arr[i] <= v while( i <= r && arr[i] < v ) i ; // 注意這里的邊界, arr[j] > v, 不能是arr[j] >= v while( j >= l 1 && arr[j] > v ) j --; if( i > j ) break; swap( arr[i] , arr[j] ); // 注意這里的交換完，需要都向前移動一位 i ; j --; } swap(arr[l], arr[j]); return j;首先要了解什么是堆，堆其實(shí)就是一個二叉樹，分為大頂推和小頂推，由小到大排序，一般小頂推。小頂堆的父節(jié)點(diǎn)的值小于兩個孩子節(jié)點(diǎn)的值。具體可以去看堆的定義，這里就不多說了。
/** * 對元素組的堆排序 */template<typename T>void heap_sort(T arr[], int length){ // 構(gòu)建堆 for(int i = (length-1)/2; i >= 0; i--){ __siftDown(arr, length, i); } for(int i = length-1; i >= 0; i--){ swap(arr[0], arr[i]); __siftDown(arr, i, 0); }}template<typename T>void __siftDown(T arr[], int length, int k){ while ( 2*k 1 < length) { int i = 2*k 1; if(i 1<length && arr[i] < arr[i 1]){ i ; } if(arr[k] >= arr[i]) break; swap(arr[k], arr[i]); k = i; }}參考：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
來源：https://www.icode9.com/content-1-656751.html