排序（數據結構）

比較排序

插入排序（斗地主摸牌就是一個插入排序）

單純的插入排序也叫直接插入排序

時間復雜度：

最好O(n)
最壞O(n^2)

過程
先寫單趟，再寫整體
依次比較，如果大于就往后挪動，否則就退出循環，插入數據

void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i-1;int tmp = a[i];//講tmp插入到[0,end]區間，保證有序//和前一次順序有關系 所以最好的時候就是O(n)while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

希爾排序（分組插排）

希爾排序也是一個插入排序，不過他對原來的插入排序做了優化
時間復雜度

O(n^1.3)

過程
1.預排序 --目標數組接近有序
2.直接插入排序

//希爾排序
//簡化寫法
//多組并排
//時間復雜度O(n^1.3)
void ShellSort(int* a, int n)
{int gap = n;//gap > 1while (gap > 1){//gap /= 2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

時間復雜度的分析

希爾排序是一個很復雜的排序，他的時間復雜度是一個增量式序列問題，如果我們只算邊界的話，它可以約等于n,但是他的中間應該是一個上升和下降的曲線。但是該怎么證明嘛，這里沒有明確的回答，涉及到了一些數學問題。正常分析可能會認為是n*logn,但是局部的結論認為他是n^1.3次方，這也是他復雜的原因，因為它沒有一個明確的證明過程，可以記一下結論。這里如果非要深究的話，和gap取值是有關的，關鍵是gap的取值不是定值，而是一直在變化。目前比較認可的取值是n/2和n/3+1。如果有興趣的話可以研究一下，但是這就涉及到一些數學領域的問題啦。

直接選擇排序

時間復雜度

O(n^2)

直接選擇排序很簡單，同時也是一個最爛的排序。
為什么說這是一個最爛的排序呢因為他的時間復雜度無論是最好還是最壞的情況都是O(n^2)，他的每一次排序都是從新選擇，和前面的排序沒有關聯。
選擇排序和插入排序的關系就像一個是斗地主的時候邊摸邊排序，一個是等發完所有的牌，再去給牌排序。

//選擇排序
//時間復雜O(n^2)
//最壞O(n^2)
//最好O(n^2)
//最垃圾的算法  他的前一次順序調整和下一次沒有關系 無論什么時候都是一個等差數列相加
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int min = left, max = left;//單躺for (int i = left + 1; i <= right; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(&a[left], &a[min]);//left 和 max重疊if (left == max){max = min;}Swap(&a[right], &a[max]);left++;right--;}
}

冒泡排序（默認升序）

時間復雜度

O(n^2)

冒泡排序屬于交換排序的一種
不做優化的情況下時間復雜度都是O(n^2)，做了優化的情況下最好的情況是O(n)
兩兩交換，一次遍歷下來肯定能能把最大值排好，他和插入排序也是一個等差數列相加。
那冒泡排序和插入排序那一個更好呢？答案是插入排序。
雖然都屬于一個量級，但是在數據是部分有序和接近有序的時候插入排序會更快，比如數據1，3，2，4，5。
大家可能不理解，不是時間復雜度都一樣了嗎？為啥還有更優的說法呢？這里時間復雜只是一個量級標準，就像我們都是在校大學生，但是大學生就沒有區別嗎？有的人早起備考四六級，考研；有的人天天宿舍打游戲，通宵熬夜。出去講，我們都會說自己是大學生，這是一個量級標準，但是你們還是很有區別。如果你非要從時間復雜度為O(n^2)選擇一個排序，那插入排序絕對是YYDS。
冒泡排序其實更多的是教學意義，實際中不太會用他。

堆排序

時間復雜度

O(n*logn)

結論

排升序，建大堆
排降序，建小堆

這里排序建堆，是有點反正常的。這里采用的是，從下向上逐漸建堆，類似于后序遍歷。建好堆(升序為例)，從堆頂取數據放到末尾，再對剩余的數組建堆(向下調整)，重復操作。這里建堆，采用向上調整和向下調整都行，這里推薦使用向下調整（一個函數搞定）這里排序見大堆還是小堆，其實不是絕對，這里推薦的是最佳的解法，如果非要使用排升序，建小堆，也不是不能實現。

//向下調整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//注意越界if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
//時間復雜度O(n*logn)
void HeapSort(int* a, int n)
{//模擬插入建堆//排升序 建大堆//排降序 減小堆//向下調整建堆 效率更高 一般使用向下調整建堆  o(n - log n)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;//這里的時間復雜度計算和向上建堆一樣 N*logNwhile (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

快速排序

時間復雜度

O(n*logn)

1962年由Hoare提出的一種二叉樹結構的交換排序，它的基本思想是，選基準值/關鍵值，把他放在一個正確的位置(比他小的放在左邊，比它大的放在右邊)，遞歸該過程。（升序為例）

結論：以左邊為基準值，先從右邊找，相遇位置一定是比key小的,以右邊為基準值，先從左邊找，相遇位置一定是比key大的。

這里分析是兩種情況，右邊先遇到左邊，左邊先遇到右邊。數據分析下就可以的出來，很簡單。
如果你是以左邊為基準值，先從左邊找，相遇位置一定是比key小的,
這個相遇位置不一定是比key小，這里隨便找一個反例，就可以得出來。

最原始的快排有個致命問題就是key值的選擇如果固定，在有序的時候，就是最壞的情況。遞歸太深了，會棧溢出。所以，這里提供了兩種解決方案，三數選中和隨機選key。這里更推薦三數選中，他完美解決了有序的情況。

這里有三種實現快速排序的方法，第一種就是最純粹的Hoare版本，但是Hoare版本不太好理解，容易寫錯。所以就有大佬進行改編，衍生出了挖坑法和前后指針法。這種方法只是對單趟的遍歷進行了改編，本質上還是快排的思想，還是遞歸，時間復雜度也是屬于O(n*logn)。這里推薦使用前后指針的方法，因為這個方法比較簡單而且不容易寫錯。
這里介紹的都是遞歸快排的寫法，但是遞歸就有一個致命問題，那就是遞歸太深會棧溢出，這其實不是代碼的問題，是編譯器的問題。所以，我們還要學習非遞歸的寫法。
三數選中

//選取中間的數
int GetMiduimNum(int* a,int left, int right)
{//int mid = left + right / 2; 錯誤寫法int mid =  left + (right - left) / 2;if (a[left] < a[mid]) // 2 < 3{if (a[right] > a[mid])//4 > 3{return mid; // 2 3 4}else if(a[left] > a[right]){return left;}else{return right;}}else //a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}}
}

Hoare

快速排序 Hoare寫法 最簡單最原始版本
最壞情況O(n^2)
最好情況O(n*logn)
時間復雜度n*logn 加了優化就可以解決有序的情況
int Part1Sort(int* a, int left, int right)
{//結束條件if (left >= right){return;}int begin = left, end = right;//隨機選Key 版本//int randi = left + (rand() % (right - left));//Swap(&a[left], &a[randi]);//三數選中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int key = left;//left++ 這是一種錯誤寫法 千萬不要寫while (left < right){//右邊找小while (left < end && a[right] >= a[key]){right--;}//左邊找大while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);key = left;return key;
}
//區間優化 減少遞歸次數 主要是遞歸深度 對性能影響不大
void QuickSort(int* a, int left, int right)
{//結束條件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part1Sort(a, left, right);//begin key -1 hole key+1 end//遞歸QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

挖坑法

//挖坑法 不再有左邊先走還是右邊先走 就是挖坑填坑 大思路不變
int Part2Sort(int* a, int left, int right)
{int begin = left, end = right;//三數選中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int hole = left;int key = a[left];while (left < right){while (left < end && a[right] >= key){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;//回坑return hole;
}
//區間優化 減少遞歸次數 主要是遞歸深度 對性能影響不大
void QuickSort(int* a, int left, int right)
{//結束條件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part2Sort(a, left, right);//begin key -1 hole key+1 end//遞歸QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

前后指針

//前后指針
int Part3Sort(int* a, int left, int right)
{int begin = left, end = right;//三數選中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int prev = left, cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
//區間優化 減少遞歸次數 主要是遞歸深度 對性能影響不大
void QuickSort(int* a, int left, int right)
{//結束條件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part3Sort(a, left, right);//begin key -1 hole key+1 end//遞歸QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

遞歸改非遞歸有兩種思路

直接改循環（斐波那契額數列）
使用棧輔助（快排）

非遞歸寫法
棧里面取一段區間，單排分割子區間入棧，子區間只有一個值或者不存在就不入棧。這里其實就是在模擬遞歸而已，不理解的話，可以畫個遞歸展開圖。
快排其實還有一個非常致命的問題就是如果存在大量重復的問題，他的效率會變得很低，這個時候三數選中和隨機選key也不管用。這個時候需要一個三路劃分

//非遞歸寫法
void QuickSort(int* a, int left, int right)
{ST stack;STInit(&stack);STPush(&stack, right);STPush(&stack, left);while (!STEmpty(&stack)){int begin = STTop(&stack);STPop(&stack);int end = STTop(&stack);STPop(&stack);//先單趟int keyi = Part3Sort(a, begin, end);//begin keyi-1 keyi keyi+1 endif (keyi + 1 < end){STPush(&stack, end);STPush(&stack, keyi+1);}if (begin < keyi -1){STPush(&stack, keyi-1);STPush(&stack, begin);}}STDestroy(&stack);
}

總結

快排類似于一個二叉樹的前序遍歷，就像先找到根，在遍歷左子樹和右子樹。快排與普通的排序相比，時間復雜度已經有了質的提升。但是快排也不是一個簡單的排序。它有許多版本，最原始的就是Hoare版本，也是很難理解的。于是后面的挖坑法和前后指針法及誕生了。這里三種方法都要學習，但是平常寫建議前后指針，這是一種比較簡單的方法(如果你能理解)

歸并排序

歸并排序類似與一個二叉樹的后序遍歷，要對一段數字排序先找到這段數字的兩個有序子區間，使用比較大小，依次取數字，進行排序。找到兩個有序子區間就是一個分割歸并過程。

遞歸實現

void _MergeSort(int* a, int begin,int end,int* tmp)
{if (begin >= end){return;}int mid = (begin + end) / 2;//[begin mid] [mid+1 end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//歸并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//歸并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1,tmp);free(tmp);tmp = NULL;
}

非遞歸實現

//非遞歸 歸并排序
void _MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2*gap){int begin1 = i, end1 = i+gap-1;int begin2 = i+gap, end2 = i+2*gap-1;//printf("[%d %d][%d %d] ", begin1, end1, begin2, end2);int j = i;//修正路線/*	if (end1 >= n){end1 = end2 = n - 1;begin2 = n;}else if (begin2 >= n){end2 = n - 1;begin2 = n;}*/if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}printf("[%d %d][%d %d] ", begin1, end1, begin2, end2);while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//0 1 2 3memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}//memcpy(a, tmp, sizeof(int) * (n));printf("\n");gap *= 2;}free(tmp);
}

非比較排序

計數排序

時間復雜度

O(n+range)

hash映射，記錄坑位數字出現的次數。當范圍很集中時，數據為int，比較適合。
局限性：對于double，字符串和很多其他情況無法完成。

void CountSort(int* a, int n)
{//找最大值和最小值int max = a[0], min = a[0];for (int i = 1; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* CountA = (int*)calloc(range, sizeof(int));//映射for (int i = 0; i < n; i++){CountA[a[i]-min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (CountA[i]--){a[j++] = i+min;}}
}