常見的排序算法分為以下四種，插入排序，選擇排序，交換排序，歸并排序。

一、插入排序

(一)直接插入排序

直接插入排序，將一段數組看做被分成已排序序列和未排序序列，排序過程是從未排序序列的元素開始，該元素與已排序序列的元素從后向前掃描，找到第一個小于（或大于）該元素的已排序項，然后將該未排序項插入到已排序序列中的適當位置。

void InsertSort(int* a, int n)
{//最后一組，[0, n-2]for (int i = 0; i < n - 1; i++)//是n不是n-1！！！{int end = i;int tmp = a[end + 1];//[0,end]是有序的，從end+1開始插入while (end >= 0){if (tmp < a[end])//比tmp值大的，往后挪{a[end + 1] = a[end];end--;}else{//不在里面放是因為，如果要插入的，比所有值都小//end此時為-1，循環結束，跳不到elsebreak;}}a[end + 1] = tmp;}
}

(二)希爾排序

希爾排序是針對直接插入排序的改進

將數組元素分為gap組，即每隔gap個的元素為一組，組內排序，然后修改gap值，當gap為1時，就是直接插入排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 2;//除幾都可以，除3比較好，但是最后不能保證是1gap = gap / 3 + 1;//這樣就保證了最后結果一定是1for (size_t i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}OP()把打印注釋//printf("gap:%2d->", gap);//PrintArray(a, n);}
}

二、選擇排序

(一)選擇排序

選擇排序，遍歷整個數組，每次選擇出最大的

進行升級，每次遍歷找出最小最大的

注意下面代碼中的
?? ??? ?if (begin == maxi)
?? ??? ?? ? maxi = mini;

這個是很有必要的

比如說begin開始是最大值，和mini交換之后，接下來最大maxi要和begin進行交換，但是begin此時的值不是最大值

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i < end; i++)//從begin+1是因為，自己跟自己比沒意義，<end也是{if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);if (begin == maxi)maxi = mini;Swap(&a[end], &a[maxi]);++begin;--end;}
}

(二)堆排序

void AdjustDown(int* a, int n, int parent)
{// 先假設左孩子小int child = parent * 2 + 1;while (child < n)  // 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;}}
}
//堆排序
void HeapSort(int* a, int n)
{// 向下調整建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

三、交換排序

(一)冒泡排序

兩層循環，內層單趟是找出最大的

void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){//里面是單趟int flag = 0;for (int j = 0; j < n - 1 - i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);flag = 1;}}if (flag == 0)break;}
}

(二)快速排序

1、hora方法

以第一個數為key，將比key小的元素放在基準元素的左邊，將比key大的元素放在基準元素的右邊。

遍歷結束后，key左邊所有的都比key小，右邊都比key大，key就排序完成了，然后在遞歸調用快排函數排序左右兩側。

但是這樣有個問題，假如數組一開始就有序，那么排序的深度很大（需要遞歸多次），這就可以使用三數取中來優化代碼，left，right，以及(left+right)/2這三個是數的下標，找到中間值給left進行交換。

同時，快排的遞歸調用類似于滿二叉樹，后三層遞歸次數占總次數很大，可以使用小區間優化，當該區間元素個數不夠時，使用一種排序方法排序，這里選擇直接插入排序，（直接插入排序在小規模數據上表現良好）。

int GetMidi(int* a, int left, int right)
{//取得是大小在中間的值int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right])return midi;else if (a[left] < a[right])//走到這里說明a[left] < a[midi], a[right] < a[midi]return right;elsereturn left;}else//a[left] >= a[midi]{if (a[midi] > a[right])return midi;else if (a[left] < a[right])return left;elsereturn right;}
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;// 小區間優化，不再遞歸分割排序，減少遞歸的次數if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);//a+left是因為InsertSort需要數組起始地址}else{// 三數取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){// 右邊找小while (begin < end && a[end] >= a[keyi]){--end;}// 左邊找大while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}//while運行完，左邊全是比key小，右邊全是比key大Swap(&a[keyi], &a[begin]);keyi = begin;// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

2、前后指針方法

prev和cur

cur先向右移動，找到比key小的，然后++prev，交換prev和cur的值

遍歷一遍，prev最后位置左邊，都是比key值小的，跟Quick相似，左邊全比他小，右邊比key大

int PartSort2(int* a, int left, int right)
{三數取中//int midi = GetMidi(a, left, right);//Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right)//還在區間{//由于一開始緊挨著，后面判斷是為了防止自己交換//順序也不能反，如果a[cur] > a[keyi]，就不會執行后面的，也就是說cur++但是prev不++if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}//不要寫else，cur無論什么情況都要++cur++;}Swap(&a[prev], &a[keyi]);return prev;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;// 小區間優化，不再遞歸分割排序，減少遞歸的次數if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);//a+left是因為InsertSort需要數組起始地址}else{int keyi = PartSort2(a,left,right);//修改此處即可// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

3、非遞歸方法

快排非遞歸 -- 數據用棧模擬（隊列也可以，隊列先進先出，數據就不用倒著進）
?用棧類似于DFS（深度優先遍歷）
?用隊列類似于BFS（廣度優先遍歷 -- 二叉樹的廣度就是層序遍歷）
遞歸會建立棧幀，（溢出跟深度有關）
在遞歸里，棧幀存的核心數據是 -- 區間（所以非遞歸方式，棧存放區間）
循環每走一次，取棧頂區間，進行單趟排序，右左子區間入棧（右左是因為棧后進先出）
?函數調用是在棧區取空間（棧只有8M）
?數據結構的棧空間不夠去擴容是在堆（堆在32位下是2G）

void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st))// 循環每走一次，相當于一次遞歸{int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort2(a, begin, end);// [begin, keyi - 1] keyi [keyi + 1, end]// 先入右[keyi + 1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}//再入左[begin, keyi - 1]if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}
}

四、歸并排序

假設把數組分成兩段，如果左右區間有序，兩個指針指向左右區間第一個，一個比另一個小，就比所有的小
把小的尾插到一個tmp數組
類似二叉樹的后序，有序就歸并，無序就遞歸

1、遞歸

void _MergeSort(int* a, int* tmp, int begin, int end)//_從習慣和風格上是子函數
{//只有一個值，返回if (begin >= end)return;int midi = (begin + end) / 2;//[begin , midi] [midi + 1, end] -- 有序就可以進行歸并//不能是[begin , midi - 1] [midi, end]!!!//假設begin=0，end=1，此時midi=0，如果-1得到的分組就是[0,-1]，[0,1]//[偶數，偶數+1]分組得到，[偶數，偶數]，[偶數，偶數+1] -- [偶數，偶數+1]一直出現，造成棧溢出x//子問題遞歸來實現有序_MergeSort(a, tmp, begin, midi);_MergeSort(a, tmp, midi + 1, end);//歸并int begin1 = begin, end1 = midi;int begin2 = midi+1, end2 = end;int i = begin;//有一個滿足是結束的條件，while循環里要寫繼續的條件！！！while (begin1 <= end1 && begin2 <=end2){if (a[begin1] <= a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//執行完之后，只排序了一個，再把兩個里面的都進一遍就行while(begin1 <= end1)tmp[i++] = a[begin1++];while(begin2 <= end2)tmp[i++] = a[begin2++];//數據還在tmp數組中，需要拷貝回去memcpy//不是拷整個區間，是begin到endmemcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}_MergeSort(a, tmp, 0, n-1);free(tmp);tmp = NULL;
}

2、非遞歸

?使用非遞歸 -- 一開始每兩個數歸并，然后每四個數歸并...把遞歸倒著看
?gap -- 每組歸并數據的數據個數(gap是其中一組歸并數據的個數)
?gap, gap 這樣歸并，所以數據個數*2
?[i, i + gap -1], [gap + i,i + 2*gap - 1]

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap)//i代表每組歸并的起始位置{//[begin1,end1][begin2,end2]//end = 起點 + 個數 - 1int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;printf("[%d, %d] [%d, %d]", begin1, end1, begin2, end2);//第二組都越界 -- [begin1,end1] n [begin2,end2]if (begin2 >= n){break;}//第二組begin2沒越界，end2越界，需要修正一下繼續歸并 -- [begin1,end1][begin2, (n) end2]if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])//歸并排序，這里加個=才是穩定的，當相等的時候取前一個tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}while (begin1 <= end1)tmp[j++] = a[begin1++];while (begin2 <= end2)tmp[j++] = a[begin2++];memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;printf("\n");}free(tmp);tmp = NULL;
}

五、各個排序的時間復雜度及穩定性

穩定性指的是相同的值排完后，相對順序不變

直接插入排序

兩層循環

時間復雜度O(N^2)，每次插入大約移動一半元素

最壞時間復雜度O(N^2)，數組完全逆序

穩定，因為插入操作不會改變相同元素的相對順序

希爾排序

時間復雜度O(N^1.3) - O(N^2)，O(N^1.3)即可

最壞時間復雜度O(N^2)，取決于分組情況gap

不穩定，元素的移動可能跨越多個間隔，導致相同元素相對順序改變

選擇排序

時間復雜度O(N^2)，每次插入大約移動一半元素

最壞時間復雜度O(N^2)，數組完全逆序

不穩定，每次選擇最小元素并交換，會改變相同元素的相對順序

堆排序

時間復雜度O(nlogn)，

最壞時間復雜度O(nlogn)，

由于堆的調整操作，無論輸入數組的初始狀態如何，時間復雜度不變

不穩定，在調整堆的過程中，會交換元素，可能改變相同元素的相對順序

冒泡排序

時間復雜度O(N^2)，

最壞時間復雜度O(N^2)，當數組完全逆序時

穩定，相鄰元素比較和交換，相同元素不會交換位置

快速排序

時間復雜度O(nlogn)，

最壞時間復雜度O(N^2)，當每次選擇的基準元素都為當前子數組中的最大或最小元素時，導致劃分極不均衡，遞歸深度達到最大

不穩定，分區過程中，基準元素的交換可能導致相同元素相對順序改變

歸并排序

時間復雜度O(nlogn)，

最壞時間復雜度O(nlogn)，

無論數組初始狀態如何，通過不斷將數組對半劃分并合并，所以其時間復雜度不會變

穩定，在合并過程中，可以保證相同元素的相對順序不變

?? ?while (begin1 <= end1 && begin2 <=end2)
?? ?{
?? ??? ?if (a[begin1] <= a[begin2])
?? ??? ??? ?tmp[i++] = a[begin1++];
?? ??? ?else
?? ??? ??? ?tmp[i++] = a[begin2++];
?? ?}

if中的<=，=可以確保相同值時相對順序不變(遞歸非遞歸都是這個=)