數據結構——排序（萬字解說）初階數據結構完

1.排序

2.實現常見的排序算法

2.1 直接插入排序

??編輯

2.2 希爾排序

2.3 直接選擇排序

2.4 堆排序

2.5 冒泡排序

2.6 快速排序

2.6.1 遞歸版本

2.6.1.1 hoare版本

2.6.1.2 挖坑法

2.6.1.3?lomuto前后指針

2.6.1.4 時間復雜度

2.6.2 非遞歸版本

2.7 歸并排序

3 性能比較

4.非比較排序

5..排序算法復雜度及穩定性分析

1.排序

排序就是排序，排序大家都不陌生，接下來跟作者一起進入學習吧！

常見的排序算法：

2.實現常見的排序算法

2.1 直接插入排序

直接插入排序是?種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到?個已經排好序的有序序列中，直到所有的記錄插?完為止，得到?個新的有序序列

?

這是張圖片，咱們先來看代碼，然后跟著代碼來分析它的思想：

void zhijiecharuSort(int* arr, int n)
{//里面挪動一大部分，外面才挪動一小部分for (int i = 0; i < n - 1; i++)//end只能到n-2，若是end到了n-1，那么tmp就越界了，無數據，無法比較了.而這個i++可以改變每次end的位置{int end = i;int tmp = arr[end + 1];while (end >= 0)//定義end的左范圍，防止越界{if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;//這個時候的end是end--后的end，所以此時的end+1的值就是之前end的值}
}

假定end為有序數據的最后一位，而tmp為待排數據的第一位。上面的排的是升序。

1.先將 tmp中的值保存進tmp，即tmp=arr[end+1]。（為了防止end位置的數據存進tmp時，tmp數據被覆蓋了，找不到）

2.將end與tmp進行比較，若end>tmp，則將end數據交給tmp，即arr[end+1]=arr[end]

3.end--；（繼續比較前面的數據）

4.將arr[end+1]=tmp從而實現了排序

5.外部i不斷地加加，內部end不斷地減減，從而實現了從一開始的位置，一直到最后的位置，每個位置都有end來從這個位置一直比較到最開始的地方。

來看動圖：

時間復雜度為n^2,這個是每次比較，都把數據給比較滿了，即1+2+3+.....+n-1=n^2。所以最差的情況就是n^2。最好的情況就是數組有序且升序，這樣話就是n個1相加，時間復雜度為n。而平均情況就是介于n^2與n之間，是小于n^2的。

所以為了接近n^2,大的數據在前，小的數據災后。這樣，越到后面，交換的次數越多。

為了接近n，小的數據在前，大的數據在后即可。

但其實，這個時間復雜度不是很好，所以咱們有一個對于它的優化版本。

2.2 希爾排序

該排序是用來優化直接插入排序的，又稱為縮小增量排序。（增量，即gap）

gap等于幾，即分成幾組，且gap只是一種距離，即gap等于5時，說明分成了5組，每個組中間有gap-1個元素。如上圖所示，這樣的前后銜接的其實是有2大組的。并且這個排序結合了直接插入排序的2個優勢：

1.增量大時，分組多，但組內元素少（一整個大組），效率高。?

2.隨著增量的減少，雖然組內的元素增加，但也越來越有序，效率也越來越高。

下面看代碼：（代碼以gap=2為例）end與tmp每次只需要往后挪動一位即可

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//n/3,n/3/3,n/3/3/3,最后gap只要取到1即可for (int i = 0; i < n - gap; i++)//i指向最后一個數的前一個指標所在的位置{//其實你內層不要管具體排的是哪一組，因為外層的++會讓每一組都排上int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;//到這就是end-=gap了}}
}

時間復雜度：

外層的時間復雜度為logn。?

?內層循環：

需要注意的是，上面所說的1+2+3+...........+(n/gap-1),這個只是取值范圍，并不是真正的2，3）。

還有就是可發現這個次數是呈現出先上升后下降的規律的，用圖表示就是：

因此，希爾排序在最初和最后的排序的次數都為n，即前?階段排序次數是逐漸上升的狀態，當到達某?頂點時，排序次數逐漸下降至n，而該頂點的計算暫時無法給出具體的計算過程?。

所以咱們給到的希爾排序的時間復雜度為n^1.3

2.3 直接選擇排序

選擇排序的基本思想：每?次從待排序的數據元素中選出最小（或最大）的?個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

?先上動圖：

?這里直接選擇排序我有兩種寫法，先來看第一種吧，我本人認為第一種是最好理解的：

void zhijieSort2(int* arr, int n)
{for (int left = 0; left < n - 1; left++) {int mini = left; // 正確初始化mini為當前leftfor (int right = left + 1; right < n; right++) {if (arr[right] < arr[mini]) {mini = right;}}Swap(&arr[mini], &arr[left]); // 直接交換到正確位置}
}

OK，咱們來看這段代碼，配合者動圖看。這段代碼的邏輯就是?我先定義最左邊的數為最小的數，之后，從左到右一次的遍歷，尋找比最左側還小的數，如果找到了，交換，交換完之后left++即可。若是沒找到，說i明最左側即最小，left也++，繼續往后比較。怎么樣，這段代碼的邏輯是不是很簡單。那么再來看第二種寫法：

void zhijieSort(int* arr, int n)
{int begin = 0;int end = n - 1;//begin，end都是下標while (begin < end){int maxi = begin;int mini = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (begin == maxi){maxi = mini;}Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);begin++;end--;}
}

這個代碼的邏輯不是那么好理解，咱們需要提前知道一個東西，就是這個方法是從左右兩邊同時開始排。即左邊排最小，右邊排最大。

咱們來看這張圖并一起來看代碼：就是讓maxi與mini一開始都指向begin，那么之后尋找maxi與mini，

1.如果maxi==begin，那么這個時候，由于要先將 mini與begin交換，但是這樣一交換之后，就會導致maxi這個地方就是mini了，那么后面的maxi與end交換，就得不到最大值了。所以咱們要先將maxi挪動到mini的位置上，這樣，就算mini與begin交換，maxi（mini）的位置還是最大值，你說對吧。這就是為什么要移動maxi位置的原因。交換后，begin++，end--繼續比較即可。

2.如果maxi！=begin，那么直接交換就可以了，不需要任何顧慮。

這樣一看，第二種方法的邏輯還是比較難理解一些的。

時間復雜度：1.直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

2.時間復雜度： O(N^2)

2.4 堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的?種排序算法，它是選擇排序的? 種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。

這個方法，咱們在上一節中重點講的這個方法，不記得的記得去回顧一下哦。

2.5 冒泡排序

交換排序基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

魚兒吐泡泡大家都見過吧，沒錯，基本就是這個思想。因為每?個元素都可以像小氣泡?樣，根據自身大小?點?點向數組的?側移動。

上圖為動圖。

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - 1 - i; j++)//j<n-1-i只起到了屏障的作用，當i增加的時候，右邊的屏障也在向左移動{if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}}
}

?其實冒泡排序本身不是很好，所以他只起到了一個教學作用。

時間復雜度：

上面的冒泡排序的時間復雜度的分析節選自《大話數據結構》P383，由此可見，冒泡排序的時間復雜度為n^2。

2.6 快速排序

快速排序是Hoare于1962年提出的?種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小?于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。?

所以，快速排序就是冒泡排序的升級版本。

2.6.1 遞歸版本

基本框架：（需要用到遞歸）

void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基準值//int keyi = _QuickSort(arr, left, right);int keyi = _QuickSort2(arr, left, right);//left  keyi  right//左序列：[left,keyi-1]   右序列：[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

那么咱們目前最主要的就是尋找基準值。從而實現劃分。?

尋找基準值的幾種方法：

2.6.1.1 hoare版本

那么這里涉及到兩個問題：

1.為什么跳出循環后right位置的值?定不大于key？?

當 l eft > right 時，即right?到left的左側，而left掃描過的數據均不大于key，因此right此時指向的數據?定不大于key。

2.為什么left和right指定的數據和key值相等時也要交換？

相等的值參與交換確實有?些額外消耗。實際還有各種復雜的場景，假設數組中的數據大量重復時，無法進行有效的分割排序。?

先來看一下代碼的基本實現思路吧：

right：從右往左找比基準值小的。

left：從左往右找比基準值大的。

找到后，讓left與right數據交換，后right--，left++，之后重復步驟即可。

當left>right時，停止?查找，讓right與基準值進行交換，且每次找到基準值后，再次分左右（分的時候不帶基準值）。

OK，下面來看代碼：

int  _QuickSort(int* arr, int left, int right)//找基準值的方法之一
{int keyi = left;++left;//left++也可以嗎？while (left <= right){if (left <= right && arr[right] > arr[keyi])//若是right先找到小的，則站那不動，直到等到left找到比基準值大的{++right;}if (left <= right && arr[left] < arr[keyi]){++left;}if (left <= right){Swap(&arr[left++], &arr[right++]);}}Swap(&arr[keyi], &arr[right]);return right;
}

原理就是這樣一個原理。小的放左邊，大的放右邊，中間的是中等大小的。最后再排成小，中，大這樣的一個即可。

2.6.1.2 挖坑法

思路：? 創建左右指針。?先從右向左找出比基準小的數據，找到后立即放?左邊坑中，當前位置變為新的"坑"，然后從左向右找出比基準大的數據，找到后?即放入右邊坑中，當前位置變為新的"坑"，結束循環后將最開始存儲的分界值放入當前的"坑"中，返回當前"坑"下標（即分界值下標）。

來看代碼：

?
int _QuickSort(int* a, int left, int right) 
{int mid = a[left];int hole = left;int key = a[hole];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;}?

來看這段代碼的邏輯吧：

首先，代碼開始部分：

int mid = a[left];

這里聲明了一個變量mid，賦值為a[left]，也就是數組最左邊的元素。

接下來：

int hole = left;

int key = a[hole];

這里hole被初始化為left，也就是基準值的位置，key存儲了基準值的數值。這里可能是在使用“挖坑法”來進行分區操作。挖坑法的思路是將基準值的位置作為初始的“坑”，然后從右往左找比基準小的數填到左邊的坑，再從左邊找比基準大的數填到右邊的坑，交替進行，直到左右指針相遇，最后將基準值填入最后的坑中。

然后進入循環：

while (left < right)

這個循環條件是左右指針還沒有相遇，繼續處理。

在循環內部，首先從右往左掃描：

while (left < right && a[right] >= key)

{--right;

}

這里，右邊的指針right向左移動，直到找到一個小于key的元素。這里需要注意的是，條件中的a[right] >= key，當元素等于key時也會停止，這可能導致分區不平衡，但在某些實現中這樣是可以接受的，不過可能會導致重復元素較多時的性能問題。

找到之后，將a[right]的值填入hole的位置：

a[hole] = a[right];

然后更新hole的位置為right，即當前的右指針位置：

hole = right;

接下來，從左往右掃描：

while (left < right && a[left] <= key)

{

++left;

}

這里，左指針left向右移動，直到找到一個大于key的元素。同樣，a[left] <= key的條件會在遇到等于key時繼續移動，這里可能需要確認是否正確，但通常這樣的處理是允許的，因為等于基準值的元素可以被分到任一邊。

找到之后，將a[left]的值填入當前的hole位置：

a[hole] = a[left];

然后更新hole的位置為left：

hole = left;

循環結束后，將基準值key填回到最后的hole位置：

a[hole] = key;

返回hole作為基準值的最終位置。

?

2.6.1.3?lomuto前后指針

創建前后指針，從左往右找比基準值小的進行交換，使得小的都排在基準值的左邊。

創建兩個前后變量prev，cur。cur從左往右找比基準值小的數據，找到后，prev++，交換prev與cur，cur++。當cur越界后，prev與基準值交換。（這樣prev左邊就是小的數據了）。但是當++prev等于cur時，就不交換了，因為他倆指向同一個位置，交換了也是白交換。?

//雙指針找基準值方法
//創建兩個變量prev，cur，cur從前往后找比基準值小的，找到之后，先讓prev++
//之后再交互prev跟cur，cur++，直到cur越界，交換prev與基準值
//這樣做的話基準值左邊全是比他小的
int _QuickSort1(int* arr, int left, int right,int n) //同名的函數
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (arr[keyi] > arr[cur] && ++prev != cur){Swap(&arr[prev], &arr[cur]);cur++;}}Swap(&arr[keyi], &arr[prev]);return prev;
}

這里有一點需要注意，就是while循環中有一個if判斷語句，這里需要說明一下：&&中若前一個條件已經被否定了，則不會執行下一個！只有前一個條件滿足時，才會執行下一個條件。

2.6.1.4 時間復雜度

時間復雜度都為nlogn。

2.6.2 非遞歸版本

用棧進行序列的存儲。可以將由基準值劃分出來的這倆序列存到棧里面，然后依次取棧頂，找到對應的序列，對它進行排序。入棧，先入左序列，或先入右序列，都是可以的。

來看代碼吧：

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);//這個是讓ps->top--，從而改變top的位置的int end = STTop(&st);STPop(&st);// 
單趟int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);}

來看這段代碼的邏輯吧：

函數內部定義了一個ST結構體的實例st，并進行了初始化。接著，將right和left依次壓入棧中。然后進入一個循環，條件是棧不為空。在循環內部，首先彈出棧頂的兩個元素作為begin和end，這表示當前要處理的子數組的左右邊界。

接下來是單趟排序的部分。這里定義了keyi為begin，也就是當前子數組的第一個元素作為基準值。然后prev和cur初始化為begin和begin+1，這看起來像是使用了一種類似于前后指針的方法來進行分區操作。在cur循環中，當a[cur]小于基準值時，prev先自增，然后如果prev不等于cur，就交換a[prev]和a[cur]的位置。這應該是將小于基準值的元素移動到prev的位置，cur繼續前進，直到遍歷完整個子數組。最后，交換基準值a[keyi]和a[prev]，將基準值放到正確的位置，此時keyi更新為prev，也就是基準值的最終位置。

完成一趟排序后，代碼將子數組分成兩部分：[begin, keyi-1]和[keyi+1, end]。接下來，檢查這兩個子數組是否需要繼續處理。如果keyi+1 < end，說明右邊的子數組還有多個元素需要排序，于是將end和keyi+1壓入棧中。同樣，如果左邊的子數組begin < keyi-1，則壓入keyi-1和begin。這樣，棧中的元素會不斷分解為更小的子數組，直到所有子數組都被處理完畢。

?

2.7 歸并排序

歸并排序算法思想：歸并排序（MERGE-SORT）是建立在歸并操作上的?種有效的排序算法,該算法是采用分治法（Divide andConquer）的?個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使?序列段間有序。若將兩個有序表合并成?個有序表，稱為二路歸并。?

在這咱們只實現遞歸版本。

?合并的時放數據時候，不要讓其從下標為0開始（有的數據下標不是0，因為int index=begin），用臨時的數組存儲臨時合并的數據。

來看代碼：

//歸并排序
//這個是遞歸，遞完之后，還會再歸回來，所以說這個地方left，mid等
//值都是隨時隨地刷新的，即每遞歸一次，這里的數據就會更新一次，這樣的話，從小將轉換成大將的
//時候，每一組小將轉換成大將的時候（即是2個數據轉成一個大數組），left，right，mid
//都可以確保他在最新的位置
void _mergeSort(int* arr, int left, int right, int *tmp/*這里定義臨時數組的目的就是為了能夠方便的存儲由小將轉變成大將存儲的地方*/)
{if (left >= right){return;}int mid = (left + right) / 2;_mergeSort(arr, left, mid, tmp);_mergeSort(arr, mid+1, right, tmp);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{//少了一個tmp[index++] = arr[begin2++];}}//到這時，有兩種情況（不滿足上面while的兩種情況）//左序列數據沒有全部放到tmp數組中//右序列數據沒有全部放到tmp數組中while(begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//tmp中有序數據導入到原數組for (int i = left; i <= right; i++){arr[i] = tmp[i];}//這兒每遞歸一次時間復雜度為n
}
void mergeSort(int* arr, int left, int right, int n)
{int* tmp = (int*)malloc(n * sizeof(int));if (tmp == NULL){perror("malloc fail!");exit(1);}_mergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;//這個的時間復雜度為logn（不就相當于二叉樹的深度嘛）
}

來看一下這段代碼中的一些東西：

這個就是往里面放的時候的邏輯。

還要注意的是，這個歸并排序并沒有開辟新的數組來存放那些小將們，還是用的原來的數組。這一點別搞錯了！?

時間復雜度：

咱們知道遞歸的時間復雜度計算方法為：

單詞遞歸的時間復雜度為n ，遞歸次數為logn（二叉樹深度），所以它的時間復雜度為O（nlogn）。

3 性能比較

那么前面的七種算法，在排序中都要進行數據的大小比較，因此這些算法也被稱為比較排序算法。那么有比較，也得有非比較呀，不慌，咱們呢先來看一下性能比較：

?由此可見，堆排序與快速排序，是最好的，最快的。

4.非比較排序

計數排序：（這個最考驗的其實就是下標的問題）

計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。操作步驟：

1）統計相同元素出現次數。

2）根據統計的結果將序列回收到原來的序列中。

那么為什么這么開空間呢？

首先，你使用最大值加1這個方法來進行開空間對于幾個小數據有用，但是萬一數據量非常大呢？就比如105，你這樣開，前面的空間不全部浪費了嗎？

第二種，按范圍開，可以是可以，但是要注意下標，下標要靈活存儲（用max-min+1確定數組的大小）。用arr[i]-min確定下標?

統計數據出現的次數，直接遍歷即可。遍歷時，碰到哪個后，直接++即可。即cout[arr[i]-min]++。

那個下標所在的數組++一次（即相同元素出現的次數）。

那么如何回到原來的那個數組上呢？給上cout[i](即相同元素出現的次數），然后，在原數組定義一個index，從0開始，arr[index]=i+min（這個是要存儲的數）。count[i]為存儲的次數。

ok,接下來請看代碼：

void CountSort(int* arr, int n)
{int min = arr[0], max = arr[0];for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//max minint range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");}memset(count, 0, sizeof(int) * range);//直接用calloc也是可以的for (int i = 0; i < n; i++){count[arr[i] - min]++;}//將次數還原到原數組中int index = 0;for (int i = 0; i < range; i++){//數據出現的次數count[i]//下標———源數據 i+minwhile (count[i]--){arr[index++] = i + min;}}
}

來讓我們分析一下這段代碼，其實邏輯挺簡單的：

函數開始部分，首先找出數組中的最小值min和最大值max。這一步通過遍歷數組完成，初始化min和max為第一個元素，然后逐個比較更新min和max。

接下來計算range = max - min + 1，這是確定數據覆蓋的范圍大小。例如，如果max是5，min是0，那么range是6（0到5共6個數）。這里需要注意當數據范圍較大的時候，可能會需要很大的內存，這也是計數排序的局限性之一。

然后分配一個大小為range的整數數組count，用于記錄每個數出現的次數。這里用了malloc分配內存，并檢查是否分配成功。之后用memset將count數組初始化為0，確保所有元素的計數從零開始。或者，用戶提到可以用calloc，這樣就不需要memset了，因為calloc會自動初始化為零。

接下來，遍歷原數組arr，對每個元素arr[i]，計算其在count數組中的位置（arr[i] - min），并將對應的count值增加1。

最后，將統計結果還原到原數組中。這里使用一個index變量來跟蹤當前要寫入的位置，然后遍歷count數組的每個位置i。對于每個count[i]，即元素i+min出現的次數，通過while循環將i+min寫入原數組count[i]次。例如，如果count[3]是2，那么原數組中會連續放入3+min兩次。

?

確實挺簡單的吧。

計數排序在數據范圍集中時，效率很高，但是適?范圍及場景有限。?

時間復雜度： O(N+range)。