2.常見八大排序算法1.排序：
排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作
2.穩(wěn)定性：
假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的
3.內(nèi)部排序：
數(shù)據(jù)元素全部放在內(nèi)存中的排序
4.外部排序：
數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序
常見排序算法圖示：
基本思想：
3.1直接插入排序插入排序可以分為直接插入排序和希爾排序，其區(qū)別就是希爾排序在直接插入排序的基礎(chǔ)上加入了預(yù)排序的過程，基本思想都是把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
基本思想：
從第二個數(shù)開始將此數(shù)據(jù)插入到前面已經(jīng)排好的有序序列中（一個數(shù)算有序），得到一個新的有序數(shù)列，依次向后取數(shù)字向前插入，直到數(shù)據(jù)全部有序為止
動圖展示：
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-RG37NaWo-1673177660020)(https://cjc-wqr.oss-cn-nanjing.aliyuncs.com/動畫.gif)]
代碼實現(xiàn)：
重慶分公司
重慶分公司
//直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i< n - 1; ++i)
{int end = i;
int tmp = a[end + 1];//記錄后一個位置的值
while (end >= 0)
{ if (tmp< a[end])//比較
{ a[end + 1] = a[end];
--end;
}
else
{ break;
}
}
a[end + 1] = tmp;
}
}復(fù)雜度及穩(wěn)定性：
3.2希爾排序時間復(fù)雜度：
- 最壞：數(shù)據(jù)為一個逆序的序列
O(N^2)- 最好：數(shù)據(jù)為一個順序有序序列
O(N)
元素集合越接近有序，直接插入排序算法的時間效率越高空間復(fù)雜度：
- 只需一個tmp變量
O(1)穩(wěn)定性：
穩(wěn)定，兩個相同數(shù)據(jù)比較時，本輪排序會停止，兩個相同數(shù)據(jù)相對順序不變
希爾排序是對直接插入排序進行優(yōu)化后的一種排序，優(yōu)化分為兩步：
- 預(yù)排序：使得數(shù)數(shù)據(jù)更加接近于有序
- 直接插入排序：在預(yù)排序過后再進行直接插入排序，使得能更加快速的完成排序
基本思路：
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數(shù)區(qū)間
gap，1+gap*n的數(shù)據(jù)可以分為一組，對每一組內(nèi)的數(shù)據(jù)進行排序。每完成一次分組排序后gap就會縮小，然后重復(fù)上述分組和排序的工作。直到gap = 1時，進行一次直接插入排序完成整個希爾排序
- gap越大，大的數(shù)可以更快到后面，小的數(shù)可以更快到前面，越不接近有序
- gap越小，數(shù)據(jù)跳動越慢，越接近有序
圖示流程：
代碼實現(xiàn)：
//希爾排序
void ShellSort(int* a, int n)
{//預(yù)排序 分成gap組
//gap >1 預(yù)排序
//gap = 1 直接插入排序
int gap = n;
while (gap >1)
{//gap = gap / 2;
gap = gap / 3 + 1; //保證除到最后一次gap一定是1
for (int i = 0; i< n - gap; ++i) //gap組并排比較
{ int end = i;
int tmp = a[end + gap];
while (end >= 0)
{ if (tmp< a[end])
{a[end + gap] = a[end];
end -= gap;
}
else
{break;
}
}
a[end + gap] = tmp;
}
}
}復(fù)雜度及穩(wěn)定性：
4.選擇排序時間復(fù)雜度：
希爾排序的時間復(fù)雜度的計算過程很復(fù)雜，這里直接記結(jié)論就好：O(N^1.3)
空間復(fù)雜度：
只需一個tmp變量，O(1)
穩(wěn)定性：不穩(wěn)定，兩個相同的數(shù)在不同的組中發(fā)生交換時相對位置可能會發(fā)生變化
基本思想：
4.1直接選擇排序選擇排序可以分為直接選擇排序和之前講過的堆排序，基本思想都是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ虼螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完
基本思想：
在元素集合中選取大的元素，若其不是這組元素的最后一個元素，則將其與這組元素的最后一個元素
end交換，然后讓最后一個元素向前移動，重復(fù)上述步驟直到排序結(jié)束
優(yōu)化后：
在元素集合中選取大與最小的數(shù)據(jù)元素，若其不是這組元素的最后一個（第一個）元素，則將其與這組元素的最后一個元素end和第一個元素begin交換，然后讓第一個元素向后移動，最后一個元素向前移動，重復(fù)上述步驟，直到集合剩余1個元素則排序結(jié)束
動圖展示：
此動圖是優(yōu)化前的流程圖，優(yōu)化后的基本思想與其類似這里我就不再畫了，相信大佬們看了這個圖就能妥妥的理解了
代碼實現(xiàn)：
//交換函數(shù)
void Swap(int* e1, int* e2)
{int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//直接選擇排序
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)
{ if (a[i]< a[mini])
{ mini = i;
}
if (a[i] >a[maxi])
{ maxi = i;
}
}
Swap(&a[begin], &a[mini]);
//如果begin和maxi重疊，第一步交換后maxi的位置會變
if (maxi == begin)
{ maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}注意：
交換begin與mini的值后，如果begin與maxi的位置重疊，那么就要將maxi賦值為mini的值，避免交換后導(dǎo)致maxi的位置發(fā)生改變
復(fù)雜度及穩(wěn)定性：
4.2.堆排序時間復(fù)雜度：
每次比較都要遍歷一遍數(shù)據(jù)，O(N^2)
空間復(fù)雜度：
只需兩個變量遍歷更新來進行交換，O(1)
穩(wěn)定性：不穩(wěn)定,在進行選擇時可能會把相同數(shù)中的后者選擇到前面，導(dǎo)致相對位置發(fā)生改變
基本思想：
堆排序在我前面的文章中有詳細(xì)的講解，這里我就只附上原碼不另外再講思路了，友友們們可以直接點擊跳轉(zhuǎn)觀看堆排序和TopK問題（點擊跳轉(zhuǎn)）
代碼實現(xiàn)：升序--建大堆：
//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下調(diào)整（建大堆）
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//假定左孩子
while (child< n)
{//大堆：保證child指向大的那個孩子
if (a[child + 1] >a[child] && child + 1< n)
{ child++;
}
//大堆：孩子大于父親就交換，并繼續(xù)向下比較調(diào)整，反之則調(diào)整結(jié)束
if (a[child] >a[parent])
{ Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{ break;
}
}
}
//堆排序
//升序：建大堆
void HeapSort(int* a, int n)
{//建堆算法
//從最后一個元素的父節(jié)點開始依次向前可以遍歷到每顆子樹的父節(jié)點
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(a, n, i);
}
int end = n - 1;
while (end >0)
{//交換首尾數(shù)據(jù)
Swap(&a[0], &a[end]);
//從首元素開始向下調(diào)整
AdjustDown(a, end, 0);
--end;
}
}**降序--建小堆：**
//交換函數(shù)
void Swap(int* p1, int* p2)
{int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下調(diào)整（建小堆）
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;//假定左孩子
while (child< n)
{//小堆：保證child指向小的那個孩子
if (a[child + 1]< a[child] && child + 1< n)
{ child++;
}
//小堆：孩子小于父親就交換，并繼續(xù)向下比較調(diào)整，反之則調(diào)整結(jié)束
if (a[child]< a[parent])
{ Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{ break;
}
}
}
//堆排序
//降序：建小堆
void HeapSort(int* a, int n)
{//建堆算法
//從最后一個元素的父節(jié)點開始依次向前可以遍歷到每顆子樹的父節(jié)點
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(a, n, i);
}
int end = n - 1;
while (end >0)
{//交換首尾數(shù)據(jù)
Swap(&a[0], &a[end]);
//從首元素開始向下調(diào)整
AdjustDown(a, end, 0);
--end;
}
}復(fù)雜度及穩(wěn)定性：
5.交換排序時間復(fù)雜度：
向下調(diào)整建堆加上數(shù)據(jù)交換，O(N * logN)
空間復(fù)雜度：
只需一個交換變量，O(1)
穩(wěn)定性：不穩(wěn)定，當(dāng)兩個相同的數(shù)值分別位于數(shù)組的首尾時，向下調(diào)整會使兩數(shù)的相對位置發(fā)生改變
基本思想：
5.1冒泡排序所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
基本思想：
冒泡排序的基本思想在我之前的文章中也有講過，友友們可以直接點擊跳轉(zhuǎn)觀看，C語言數(shù)組詳解（點擊跳轉(zhuǎn)）
動圖展示：
代碼實現(xiàn)：
這里代碼實現(xiàn)部分相較于之前的會有一丟丟的改進，一趟冒泡排序中，如果沒有發(fā)生交換，說明已經(jīng)有序了，不需要再處理，可以直接結(jié)束排序
//冒泡排序
void BubbleSort(int* a, int n)
{//總趟數(shù)
for (int i = 0; i< n - 1; ++i)
{int exchange = 0;
//每趟交換次數(shù)
for (int j = 0; j< n - 1 - i; ++j)
{ if (a[j] >a[j + 1])
{ Swap(&a[j], &a[j + 1]);
exchange = 1;
}
}
//一趟冒泡排序中，如果沒有發(fā)生交換，說明已經(jīng)有序了，不需要再處理
if (exchange == 0)
{ break;
}
}
}復(fù)雜度及穩(wěn)定性：
5.2快速排序時間復(fù)雜度：
冒泡排序的遍歷是一個等差數(shù)列，O(N^2)
空間復(fù)雜度：
只需要一個變量來輔助交換，O(1)
穩(wěn)定性：穩(wěn)定，兩個相同的數(shù)相遇時則不需要再進行交換了，相對位置沒有發(fā)生改變
本篇文章的大哥快排來了，實現(xiàn)方法和優(yōu)化思路都是非常重要的，友友們可要打起精神了！
基本思路：
5.2.1快排遞歸實現(xiàn)任取待排序元素序列中的某元素作為基準(zhǔn)值
key，按照該基準(zhǔn)值將待排序集合分割成兩個子序列，左子序列中所有元素均小于key，右子序列中所有元素均大于key，然后在左右子序列中重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止
注意：
左邊做key，右邊先走，右邊做key，左邊先走 保證相遇位置的值比key要小
相遇的情況：
1.right停住，left遇到right，相遇位置就是right停住的位置，此時的值比key小
2.left停住，right遇到left，由于是right先走的，此時left就是起始沒動的位置key
代碼實現(xiàn)：
//快速排序（遞歸版）
void QuickSort(int* a, int begin, int end)
{if (begin >= end)
{return;
}
int left = begin, right = end;
int keyi = left;
while (left< right)
{//右邊先走，找小于key的數(shù)
while (left< right && a[right] >= a[keyi])
{ --right;
}
//左邊再走，找大于key的數(shù)
while (left< right && a[left]<= a[keyi])
{ ++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
//此時key左邊區(qū)間比key小，右邊區(qū)間比key大
//區(qū)間劃分：[begin,keti-1] keyi [keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}除了以上的普通實現(xiàn)以外，我們常見的快排實現(xiàn)方法有三種，分別是：Hoare法（霍爾法）、挖坑法、雙指針法
基本思想：
快排的則整體思想上面已經(jīng)講述過了，這里來講解一下Hoare法的具體步驟：
- 選取數(shù)據(jù)序列最左邊的值為
key- 先從序列最右邊向左走，找到
<=key的值后停下，然后從序列最左邊向右走，找到>key的值后停下- 此時交換兩處位置的值，并重復(fù)上述步驟直到左右相遇為止
- 然后后交換相遇位置的值與
key位置的值即可達到一趟快排的目的- 最后分別遞歸左右區(qū)間即可完成本次快排
動圖展示：
以上是單趟Hoare法快排的動態(tài)流程圖，相信觀看過后整體的快排也難不倒你
代碼展示：
//Hoare法
int PartSort1(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int keyi = left;
while (left< right)
{//右邊先走，找小
while (left< right && a[right] >= a[keyi])
{ --right;
}
//左邊先走，找大knm
while (left< right && a[left]<= a[keyi])
{ ++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin >= end)
{return;
}
// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
if ((end - begin + 1)< 15)
{InsertSort(a + begin, end - begin + 1);
}
else
{int keyi = PartSort1(a, begin, end);
//區(qū)間劃分：[begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}基本思想：
挖坑法相較于Hoare法引入了坑的概念更加方便理解，具體步驟如下：
- 選取序列最左邊的值為
key，并在此位置挖坑- 然后先從序列最右邊向左邊走，找到
<=key的值，就將次值填到坑中，然后從序列最左邊向右邊走，找到>key的值，就將此值填入坑中- 重復(fù)上述步驟，直到左右相遇為止
- 此時相遇點必然是一個
坑，將key填入其中本趟的快排就結(jié)束了
動圖展示：
以上是單趟挖坑法快排的動態(tài)流程圖，相信觀看過后整體的快排也難不倒你
代碼實現(xiàn)：
//挖坑法
int PartSort2(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int hole = left;
while (left< right)
{//右邊找小，填到左坑
while (left< right && 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 begin, int end)
{if (begin >= end)
{return;
}
// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
if ((end - begin + 1)< 15)
{InsertSort(a + begin, end - begin + 1);
}
else
{int keyi = PartSort2(a, begin, end);
//區(qū)間劃分：[begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}基本思想：
雙指針法快排的實現(xiàn)就與上面的兩種方法有些不同了，下面我們來看具體步驟：
- 選取序列最左邊的值為
key- 首先定義兩個指針
prev指針指向序列的開頭，cur指針指向prev的后一個位置- 判斷
cur指向的數(shù)據(jù)是否小于key,若小于則先將prev后移一位，再交換prev與cur位置的值，然后將cur后移一位，反之只將cur后移一位- 重復(fù)上述步驟，直到
cur越界，此時將prev處的值與key交換就完成了本趟快排
動圖展示：
以上是單趟雙指針法快排的動態(tài)流程圖，相信觀看過后整體的快排也難不倒你
代碼實現(xiàn)：
//雙指針法
int PartSort3(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur<= end)
{//找到比key小的值，跟++prev位置交換，小的往前翻，大的往后翻
if (a[cur]< a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
//快速排序
void QuickSort(int* a, int begin, int end)
{if (begin >= end)
{return;
}
if ((end - begin + 1)< 15)
{// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)
InsertSort(a + begin, end - begin + 1);
}
else
{int keyi = PartSort3(a, begin, end);
//區(qū)間劃分：[begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
遞歸版本的快排雖然實現(xiàn)起來更加簡單，但是如果數(shù)據(jù)量過大，就可能出現(xiàn)棧溢出的問題，這時我們就要考慮使用迭代版本的快排了，迭代版的快排是利用棧這一數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的
基本思想：
無論是遞歸還是迭代我們每一步的主要目的都是需要完成
區(qū)間劃分，利用棧的先進后出的特點，我們用以下步驟來完成目的：
- 先將數(shù)據(jù)序列的首尾元素
begin和end入棧- 進行出棧操作得到一個區(qū)間
[left，righr]（由于棧的特性，這里的left對應(yīng)的是原end的值，另一個同理）- 根據(jù)得到的區(qū)間利用
雙指針法進行選key區(qū)間劃分，并記錄key的位置- 判斷
key-1是否大于left，若是則說明左半?yún)^(qū)間合法，就可以將區(qū)間邊界left與key-1入棧；同理判斷key+1是否小于right，若是則說明右半?yún)^(qū)間合法，就可以將區(qū)間邊界入棧了- 區(qū)間被一直劃分這就與遞歸的思想有一點類似了，一直重復(fù)上述步驟直到
所有區(qū)間都非法，即棧空了，則整個迭代版本的快排就結(jié)束了
代碼實現(xiàn)
為了方便觀看和理解，代碼中涉及到的棧的部分接口的實現(xiàn)我省略掉了，想了解的友友們可以去看我之前的文章棧（C語言實現(xiàn)）(點擊跳轉(zhuǎn))
//快速排序（迭代實現(xiàn)）
void QuickSortNonR(int* a, int begin, int end)
{ST st;
StackInit(&st);
//首尾入棧
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
//利用雙指針法選key
int keyi = PartSort3(a, left, right);
//區(qū)間劃分：[left, keyi-1] keyi [keyi+1, right]
//判斷是否符合入棧條件
if (keyi + 1< right)
{ StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (left< keyi - 1)
{ StackPush(&st, left);
StackPush(&st, keyi - 1);
}
}
StackDestroy(&st);
}重難點來了！細(xì)細(xì)品味！這里提供三步優(yōu)化方法：
優(yōu)化一：三數(shù)取中 / 隨機選key
如果數(shù)據(jù)接近有序或者逆序，對于快排來說時間復(fù)雜度是較高的，因為快排選
key始終是最左或者最右的，就有可能選到大數(shù)或者最小數(shù)導(dǎo)致要把所有數(shù)據(jù)遍歷一遍，這里采用
三數(shù)取中：取三個數(shù)的中間大小的值，例如3、1、2取2隨機選key：隨機選取數(shù)據(jù)序列中的數(shù)字做key對于一些特殊測試用例，如果我們嚴(yán)格走
三數(shù)取中，可能大量區(qū)間選key會選到比較小或者比較大的值，導(dǎo)致性能下降。這時我們就可以結(jié)合隨機選key來優(yōu)化，不過因為是隨機的除了特殊用例，整體上還是三數(shù)取中比較好
代碼實現(xiàn)：
三數(shù)取中：
//三數(shù)取中
//begin< mid< end 取mid
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;
if (a[mid] >a[begin])
{if (a[mid]< a[end])
{ return mid;
}
else if (a[begin]< a[end])
{ return begin;
}
else
{ return end;
}
}
else //a[mid]< a[begin]
{if (a[end]< a[mid])
{ return mid;
}
else if (a[begin]< a[end])
{ return begin;
}
else
{ return end;
}
}
}隨機選key：
//隨機選key
int GetMidIndex(int* a, int begin, int end)
{int mid = begin + rand() % (end - begin);//保證隨機選的key在區(qū)間內(nèi)
if (a[begin] >a[mid])
{if (a[begin]< a[end])
{ return begin;
}
else if (a[end]< a[mid])
{ return mid;
}
else
{ return end;
}
}
else //a[begin]< a[mid]
{if (a[mid]< a[end])
{ return mid;
}
else if (a[end]< a[begin])
{ return begin;
}
else
{ return end;
}
}
}優(yōu)化二：小區(qū)間優(yōu)化
對于遞歸來說，越是遞歸到最后的小區(qū)間，耗費的時間就越長，這個時候我們選擇在小區(qū)間使用
直接插入排序進行代替可以很好的彌補遞歸快排在小區(qū)間排序中的缺陷，大大減少了遞歸次數(shù)，這里我們將15定為小區(qū)間
代碼實現(xiàn)：
void QuickSort(int* a, int begin, int end)
{if (begin >= end)
{return;
}
// 優(yōu)化一：小區(qū)間用直接插入代替，減少遞歸調(diào)用次數(shù)
if ((end - begin + 1)< 15)
{InsertSort(a + begin, end - begin + 1);
}
else
{// 優(yōu)化二：三數(shù)取中，避免選的key是大或最小遍歷次數(shù)太多
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int keyi = left;
while (left< right)
{ //右邊先走，找小于key的數(shù)
while (left< right && a[right] >= a[keyi])
{ --right;
}
//左邊再走，找大于key的數(shù)
while (left< right && a[left]<= a[keyi])
{ ++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
//此時key左邊區(qū)間比key小，右邊區(qū)間比key大
//區(qū)間劃分：[begin,keti-1] keyi [keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}優(yōu)化三：三路劃分
如果數(shù)據(jù)序列中與
key相同的值太多，比如數(shù)值全等于key，算法效率就會退化到O(N^2)，這時我們使用三路劃分來進行優(yōu)化，就能很好的彌補這一缺陷，具體步驟如下：
- 與key相等的數(shù)往后推
- 小于key的數(shù)甩到左邊
- 大于key的數(shù)甩到右邊
- 與key相等的數(shù)就在中間部分了
代碼實現(xiàn)：
void QuickSort(int* a, int begin, int end)
{if (begin >= end)
{return;
}
// 優(yōu)化一：小區(qū)間用直接插入代替，減少遞歸調(diào)用次數(shù)
if ((end - begin + 1)< 15)
{InsertSort(a + begin, end - begin + 1);
}
else
{// 優(yōu)化二：三數(shù)取中，避免選的key是大或最小遍歷次數(shù)太多
int mid = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = a[left];
int cur = begin + 1;
while (cur<= right)
{ if (a[cur]< key)
{ Swap(&a[cur], &a[left]);
cur++;
left++;
}
else if (a[cur] >key)
{ Swap(&a[cur], &a[right]);
--right;
}
else //a[cur] == key
{ cur++;
}
}
//三路劃分優(yōu)化后
//三個區(qū)間分別是key 1[begin,left-1] 2[left,right] 3[right+1,end]
//此時只用遞歸快排1、3區(qū)間即可
QuickSort(a, begin, left - 1);
QuickSort(a, right + 1, end);
}
} 復(fù)雜度及穩(wěn)定性（優(yōu)化后）：
6.歸并排序時間復(fù)雜度：
O(N*logN)
空間復(fù)雜度：O(logN)
穩(wěn)點性：不穩(wěn)定，兩個相同的數(shù)，后者與key交換后相對位置就會發(fā)生改變
基本思想
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并
歸并流程圖
基本思路
我們需要得到有序子序列，再將其合并得到新的有序序列，這就要用到遞歸來實現(xiàn)了，具體步驟如下：
- 將原序列分解為左右兩個區(qū)間
- 為了使區(qū)間內(nèi)數(shù)據(jù)有序，我們需要依靠遞歸，不斷
遞出分解區(qū)間直到區(qū)間內(nèi)數(shù)據(jù)只剩一個（一個數(shù)據(jù)是被認(rèn)為有序的）- 再執(zhí)行合并操作，
向上回歸合并，使得每次合并的區(qū)間內(nèi)數(shù)據(jù)都是有序的，當(dāng)回歸結(jié)束后歸并排序也就結(jié)束了，數(shù)據(jù)整體就有序了友友們可以看看上面的歸并流程圖，更好理解
動圖展示：
代碼實現(xiàn)：
//歸并排序（遞歸實現(xiàn)）子函數(shù)
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)
return;
int mid = (begin + end) / 2;
//遞歸使子區(qū)間有序: [begin,mid] [mid+1,end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//歸并：[begin,mid] [mid+1,end]
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1<= end1 && begin2<= end2)
{//兩個區(qū)間取小的數(shù)尾插
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++];
}
//將歸并排序后的數(shù)組拷貝回原數(shù)組
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//歸并排序（遞歸實現(xiàn)）
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{perror("fail malloc");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}復(fù)雜度及穩(wěn)定性：
6.2歸并迭代實現(xiàn)時間復(fù)雜度：
歸并排序就是分治的思想，O(N*logN)
空間復(fù)雜度：
歸并需要開辟額外的空間，O(N)
穩(wěn)定性：穩(wěn)定，兩個相同的數(shù)，在合并數(shù)組的過程中，前者總是會比后者先合并進數(shù)組，相對位置并不會發(fā)生改變
基本思想：
歸并的迭代實現(xiàn)只需定義一個范圍
rangeN（默認(rèn)為1），遍歷整個數(shù)據(jù)序列對rangeN范圍內(nèi)的數(shù)據(jù)進行合并，使rangeN逐漸擴大，直到rangeN >n(數(shù)據(jù)個數(shù))，此時的歸并范圍超出循環(huán)停止，整個迭代版本的歸并排序也就完成了
注意！
歸并排序的迭代實現(xiàn)的
邊界問題很難控制，一不小心就會發(fā)生越界
有以下三種越界情況：
下面我們來用兩種方法進行控制：
方法一：直接跳出
我們將合并排序后的數(shù)組拷貝回原數(shù)組有兩種方法：一是歸并一部分拷貝一部分，二是歸并完成后整體拷貝
使用直接跳出的方法來控制范圍，在拷貝時只能歸并一部分拷貝一部分
//1.end1 begin2 end2 越界
if (end1 >= n)
{break;
}
//2.begin2 end2 越界
else if (begin2 >= n)
{break;
}
//3.end2 越界
else if (end2 >= n)
{//修正到區(qū)間末尾
end2 = n - 1;
}方法二：區(qū)間修正
使用區(qū)間的方法來控制范圍，在拷貝時使用歸并一部分拷貝一部分或者整體拷貝都是可行的
//1.end1 begin2 end2 越界
if (end1 >= n)
{//修正到區(qū)間末尾
end1 = n - 1;
//修正到不存在的區(qū)間（下面的歸并循環(huán)不會進去）
begin2 = n;
end2 = n - 1;
}
//2.begin2 end2 越界
else if (begin2 >= n)
{//修正到不存在的區(qū)間
begin2 = n;
end2 = n - 1;
}
//3.end2 越界
else if (end2 >= n)
{//修正到區(qū)間末尾
end2 = n - 1;
}這里我們把兩種拷貝方法和兩種控制界限的方法都在代碼中體現(xiàn)一下
代碼實現(xiàn)：
整體歸并完了再拷貝&區(qū)間修正：
//歸并排序迭代實現(xiàn)
//整體歸并完了再拷貝
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{perror("malloc fail");
exit(-1);
}
//歸并每組數(shù)據(jù)個數(shù)，從每組1個數(shù)開始，因為1個數(shù)可以認(rèn)為是有序的，可以直接歸并
int rangeN = 1;
while (rangeN< n)
{for (int i = 0; i< n; i += 2 * rangeN)
{ //[begin1,end1] [begin2,end2] 歸并
int begin1 = i, end1 = i + rangeN - 1;
int begin2 = i + rangeN, end2 = i + rangeN * 2 - 1;
//打印一下歸并區(qū)間，便于觀察
printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
int j = i;
//對于三種越界情況來修區(qū)間 -->拷貝數(shù)據(jù)：整體歸并完了拷貝 or 歸并一部分拷貝一部分
//1.end1 begin2 end2 越界
if (end1 >= n)
{ //修正到區(qū)間末尾
end1 = n - 1;
//修正到不存在的區(qū)間（下面的歸并循環(huán)不會進去）
begin2 = n;
end2 = n - 1;
}
//2.begin2 end2 越界
else if (begin2 >= n)
{ //修正到不存在的區(qū)間
begin2 = n;
end2 = n - 1;
}
//3.end2 越界
else if (end2 >= n)
{ //修正到區(qū)間末尾
end2 = n - 1;
}
//兩個區(qū)間取小的數(shù)歸并尾插
while (begin1<= end1 && begin2<= end2)
{ if (a[begin1]<= a[begin2])
{tmp[j++] = a[begin1++];
}
else
{tmp[j++] = a[begin2++];
}
}
//一個區(qū)間遍歷完了，另一個還沒有
while (begin1<= end1)
{ tmp[j++] = a[begin1++];
}
while (begin2<= end2)
{ tmp[j++] = a[begin2++];
}
}
//整體歸并完了再拷貝
memcpy(a, tmp, sizeof(int) * (n));
rangeN *= 2;
}
free(tmp);
tmp = NULL;
}歸并一部分拷貝一部分&直接跳出：
//歸并排序迭代實現(xiàn)
//歸并一部分拷貝一部分
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{perror("malloc fail");
exit(-1);
}
//歸并每組數(shù)據(jù)個數(shù)，歸并每組從1開始，因為一個數(shù)可以認(rèn)為是有序的，可以直接歸并
int rangeN = 1;
while (rangeN< n)
{for (int i = 0; i< n; i += rangeN * 2)
{ //[begin1,end1],[begin2,end2] 歸并
int begin1 = i, end1 = i + rangeN - 1;
int begin2 = i + rangeN, end2 = i + rangeN * 2 - 1;
//打印區(qū)間，便于觀察
printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
int j = i;
//對于三種越界情況來修區(qū)間 -->拷貝數(shù)據(jù)：整體歸并完了拷貝 or 歸并一部分拷貝一部分
//1.end1 begin2 end2 越界
if (end1 >= n)
{ break;
}
//2.begin2 end2 越界
else if (begin2 >= n)
{ break;
}
//3.end2 越界
else if (end2 >= n)
{ //修正到區(qū)間末尾
end2 = n - 1;
}
//兩個區(qū)間取小的數(shù)尾插
while (begin1<= end1 && begin2<= end2)
{ if (a[begin1]<= a[begin2])
{tmp[j++] = a[begin1++];
}
else
{tmp[j++] = a[begin2++];
}
}
//如果一個區(qū)間遍歷完了，另一個還沒有
while (begin1<= end1)
{ tmp[j++] = a[begin1++];
}
while (begin2<= end2)
{ tmp[j++] = a[begin2++];
}
//歸并一部分，拷貝一部分
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
rangeN *= 2;
}
free(tmp);
tmp = NULL;
}復(fù)雜度及穩(wěn)定性：
7.計數(shù)排序同歸并排序的遞歸實現(xiàn)
基本思想：
計數(shù)排序主要是利用
映射來完成的，具體步驟如下：
- 統(tǒng)計相同元素出現(xiàn)的次數(shù)
- 將待排序數(shù)據(jù)序列
映射到計數(shù)空間中對應(yīng)下標(biāo)的位置，該位置對應(yīng)的值就是該數(shù)據(jù)出現(xiàn)的次數(shù)映射完成后，遍歷計數(shù)空間，將有值的位置根據(jù)次數(shù)重新賦值到原有序序列中，計數(shù)空間遍歷完后計數(shù)排序也就完成了
優(yōu)化：
上面的映射方式屬于
絕對映射：開辟的計數(shù)空間大?。捍笾?+ 1，也就是每個數(shù)據(jù)映射到自己對應(yīng)的下標(biāo)。如果數(shù)據(jù)序列中都是一些很大的值，這樣開辟的計數(shù)空間就會造成大量浪費，針對這一問題，我們將其優(yōu)化為相對映射：開辟的計數(shù)空間大小 = 大值 - 最小值 + 1就能很好的解決
計數(shù)排序流程圖：
代碼實現(xiàn)：
//計數(shù)排序
void CountSort(int* a, int n)
{int max = a[0], min = a[0];
for (int i = 1; i< n; ++i)
{if (a[i]< min)
min = a[i];
if (a[i] >max)
max = a[i];
}
//相對映射開辟空間
int range = max - min + 1;
int* countA = (int*)calloc(range, sizeof(int));
if (countA == NULL)
{perror("calloc fail");
exit(-1);
}
//1.統(tǒng)計數(shù)據(jù)出現(xiàn)次數(shù)
for (int i = 0; i< n; ++i)
{countA[a[i] - min]++;
}
//2.放回原數(shù)據(jù)序列排序
int k = 0;
for (int j = 0; j< range; ++j)
{while (countA[j]--)
{ a[k++] = j + min;
}
free(countA);
}
}復(fù)雜度及穩(wěn)定性：
時間復(fù)雜度：
先遍歷了一遍原數(shù)據(jù)，再遍歷了一遍計數(shù)空間，O(N + Range)
空間復(fù)雜度：
需要開辟計數(shù)空間，O(max - min)
穩(wěn)定性：穩(wěn)定，計數(shù)排序是直接覆蓋原數(shù)組
注意：
8.八大排序總結(jié)表計數(shù)排序雖然是個效率很高的排序，但是它只適合
范圍集中的數(shù)據(jù)，且只適合整形
| 排序方法 | 時間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|
| 直接插入排序 | O(N^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(N^1.3) | O(1) | 穩(wěn)定 |
| 直接選擇排序 | O(N^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(N*logN) | O(1) | 不i穩(wěn)定 |
| 冒泡排序 | O(N^2) | O(1) | 穩(wěn)定 |
| 快速排序(遞歸) | O(N*logN) | O(logN) | 不穩(wěn)定 |
| 歸并排序(遞歸) | O(N*logN) | O(N) | 穩(wěn)定 |
| 計數(shù)排序 | O(N) | O(max-min) | 穩(wěn)定 |
八大排序的實現(xiàn)到這里就介紹結(jié)束了，期待大佬們的三連！你們的支持是我大的動力！
文章有寫的不足或是錯誤的地方，歡迎評論或私信指出，我會在第一時間改正。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
