前言
排序是數據結構中很重要的一章，先介紹幾個基本概念。
- 排序穩定性：多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次
- 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
- 內部排序：數據元素全部放在內存中的排序。
- 外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
一、插入排序
時間復雜度
最壞：-----------o(n^2)
最好：-----------o(n)
平均：-----------o(n^2)
空間復雜度
o(1)
穩定性：穩定
-『 插入排序 』：顧名思義就是把每一個數插入到有序數組中對應的位置。
就相當于你玩撲克牌的過程，抓來一張牌，就放在對應有序位置
直接插入排序：
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
代碼實現（升序）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void insertsort(int* a, int n){ for (int i = 0; i < n - 1; i++) { int x = a[end+1];//x為待排序的值 int end = i;//從end開始往前和x依次比較 while (end >= 0) { if (a[end] > x)//只要當前的值大于x繼續往前找 { a[end+1] = a[end]; end--; } else { break;//跳出循環說明a[end] <= x } } a[end + 1] = x;//跳出循環說明a[end] <= x，需要把x插入到end前邊 }} |
那么我們可以看到，越是接近有序的數組，插入排序的效率越高（有序時對于任何一個數只需要和前邊的數比較一次）。
二、希爾排序
時間復雜度
o(n^（1.3—2）)
空間復雜度
o(1)
穩定性：穩定
『 希爾排序 』(shell's sort)是插入排序的一種又稱“縮小增量排序”（diminishing increment sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 d.l.shell 于 1959 年提出而得名。
該方法實質上是一種『 分組插入 』方法,因為插入排序對于接近有序的數組排序效率非常高，那么希爾提出：
算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行分組，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
并且插入排序可以看成分組是1的希爾排序。動圖如下：
因為插入排序可以看做gap==1的希爾排序，因此只需要改變插入排序中for循環的增量控制排序即可。
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
void shellsort(int* a, int n){ //按gap分組進行預排序 int gap = n; while (gap>1) { //gap = gap / 2; gap = gap / 3 + 1;//這里分組選每次折半或者/3都可以 for (int j = 0; j < gap; j++)//gap個組 for (int i = j; i < n - gap; i+=gap)//每個組從j開始每個增量gap { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } }} |
關于希爾排序時間復雜度證明比較復雜，取決于gap怎么取，如果按照knuth提出的/3，來取是o(n^（1.25）- 1.6*o(n^1.25).
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優化。
- 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定
三、選擇排序
時間復雜度
最壞：-----------o(n^2)
最好：-----------o(n^2)
平均：-----------o(n^2)
空間復雜度
o(1)
穩定性：不穩定
『 基本思想 』：
每一次從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始（末尾）位置，直到全部待排序的數據元素排完 。如圖：
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void selectsort(int* a, int n){ int begin = 0; int end = n - 1; int mini = begin;//記錄最小值下標 while (begin<end) { for (int i = begin; i < end; i++) { if (a[i] < a[mini]) { mini = i;//更新最小值下標 } } swap(&a[mini],&a[begin]);//把最小值放到左邊 ++begin;//左邊對應起始位置++ }} |
直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用。
四、堆排序
時間復雜度
最壞：-----------o(n * logn)
最壞：-----------o(n * logn)
平均：-----------o(n*logn)
空間復雜度
o(1)
堆排序(heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。
具體可見另一篇文章堆排序和topk問題
動圖：
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
void swap(int* px,int* py){ int t = (*px); (*px) = (*py); (*py)= t ;}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; } }}void heapsort(int* a, int n){ for (int i = (n - 1 - 1) / 2; i >= 0; i--) { adjustdown(a, n, i); } for (int i = n - 1; i > 0; i--) { swap(&a[0], &a[i]); adjustdown(a, i, 0); }} |
五、冒泡排序
時間復雜度
最壞：-----------o(n^2)
最好：-----------o(n)
平均：-----------o(n^2)
空間復雜度
o(1)
『 冒泡排序 』是大家最熟悉的也是最容易理解的排序,如下圖：
『 冒泡排序基本思想 』就是每一次將相鄰的數據進行『 兩兩比較 』，選出最大的依次比較送到右邊，那么最右邊就是最大值，而左邊留下的自然就是小的（排升序）
-『 冒泡排序 』需要兩層循環
『 內層循環 』表示一次冒泡，也就是兩兩比較先選出最大的放到最右邊，同時注意每一次冒泡選出最大元素，那么兩兩比較次數-1（下一次不用比較選好的最右邊）
『 外層循環 』控制的是冒泡的次數（假設數組n 個元素）也就是n-1次冒泡選出n-1個最大的元素
代碼實現
初版代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//初版：void swap(int* px, int* py){ int t = (*px); *px = (*py); (*py) = t;}void bubblesort(int* a, int n){ for (int i = 0; i < n-1; i++)//外層循環 { for (int j = 0; j < n-1-i; j++) { if(a[j]>a[j+1]) swap(&a[j],& a[j + 1]);//交換 flag = 1; } }} |
時間復雜度分析：每一次比較次數是n-1,n-2,n-3***1.因此是n(n-1)/2
但是這種寫法還是有缺陷，時間復雜度永遠是o(n^2） ， 對于一個已經排好序的數組來說，還是需要n^2的復雜度，但對于有序的數組，每一次冒泡都不會進行交換因為有序，因此如果只要任何一次冒泡中沒有數據交換就證明數組有序了。時間復雜度最好也可以達到0(n)。
代碼優化如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
//優化：void bubblesort(int* a, int n){ for (int i = 0; i < n-1; i++) { int flag = 0; for (int j = 0; j < n-1-i; j++) { if(a[j]>a[j+1]) swap(&a[j],& a[j + 1]); flag = 1; } if (flag == 0) break; }} |
六、快排排序
時間復雜度
最壞：-----------o(n^2)
最好：-----------o(logn)
平均：-----------o(logn)
空間復雜度
o(logn)
『 快速排序 』是hoare于1962年提出的一種二叉樹結構的交換排序方法，其『 基本思想 』為：任取待排序元素序列中的某元素作為『 基準值 』，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。如圖：
代碼實現
遞歸寫法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 假設按照升序對a數組中[left, right)區間中的元素進行排序void quicksort(int* a, int left, int right) { if(right >= left ) return;//遞歸截止條件 // 按照基準值對a數組的 [left, right]區間中的元素進行劃分 int keyi= partion(a, left, right); // 劃分成功后以keyi為邊界形成了左右兩部分 [left, keyi-1] 和 [keyi+1, right] // 遞歸排[left, keyi-1] quicksort(a, left, keyi-1); // 遞歸排[keyi+1, right] quicksort(a, keyi+1, right);} |
遞歸框架寫完了接下來就差partion函數的實現也就是快排的靈魂，去每一次找基準值。那么一共有三種寫法如下：
hoare版本
1.首先就是要找基準值，這里你可以選最左邊或最右邊的值（圖中是6）
2.兩個指針指向頭（這里選左為基準值，頭指針指向第二個）和尾，基準值選左，則右指針先走，反之左指針先走。
3.左指針找到比基準值大的停下，右指針找比基準值小的停下，交換左右指針指向值
4.重復2.3動作，直到左右指針相遇，交換左指針值和基準值
左值為基準，右指針先走找比6小的：
左值為基準，右指針先走找比6小的：
交換：
最終效果：相遇交換左指針和基準值，保證了6的左邊都比6小，右邊比6大。
并且除此之外，由于我們看到這種算法類似于二叉樹的思想排好中間再排左右子樹，因此我要保證選取的隨機值盡量位與中位數。所以我們采取三數取中的方法。（選取最左值最右最中間的數的中位數）效率是可以提升5%到10%的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
//三數取中int getmidindex(int* a, int left, int right){ //int mid = (left + right) / 2; //int mid = left + (right - left) / 2; int mid = left + ((right - left)>>1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } 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 left; } else { return right; } }}int partion(int* a, int left,int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int keyi = left; while (left < right) { while (left < right && a[right] >= a[keyi]) { right--; } while (left < right && a[left] <= a[keyi]) { left++; } swap(&a[left], &a[right]); }swap(&a[left], &a[keyi]); return left;} |
挖坑法
挖坑法就是對hoare版本的一種變形，過程如下：
初始如下：先保存基準值，基準值形成一個坑位！
左為基準，右指針先走，找到小的送到坑位，那么此刻右指針形成了新的坑位
左指針出動，找到大的繼續送到坑位，左指針形成了新的坑位
指針相遇，把6寫入。也保證左邊比6小，右邊比6大。代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
//挖坑法int partion2(int* a, int left, int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int key = a[left]; int pivot = left; while (left < right) { //右邊先找小 while (left< right && a[right] >= key) { --right; } a[pivot] = a[right]; pivot = right; while (left < right && a[left] <= key) { ++left; } a[pivot] = a[left]; pivot = left; } a[pivot] = key; return pivot;} |
前后指針版本
顧名思義，使用兩個指針，這里選取左為基準值為例，兩個指針從左開始出發一個cur,一個prev。
要求：
cur指針先走，一旦找到比基準值小的就停下，++prev,并交換。
cur指針一直到頭為止，最后交換prev指向值和基準值
1和2都比6小cur走一步停一步，prev++并交換，指向相等。
cur越過7和9去找小的3，此時停下，prev++指向7交換。（我們注意到prev和cur不等時prev永遠是去找大的，cur是找小的，因此交換就做到把cur指向的小的往前扔，大的往后仍，）
整個過程如上，代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//前后指針法int partion3(int* a, int left, int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int prev = left, cur = left+1; int keyi = left; while (cur<=right) { if (a[cur] < a[keyi] && ++prev !=cur) { swap(&a[prev], &a[cur]); } cur++; } swap(&a[prev], &a[keyi]); return prev;} |
小結
遞歸版本三種方法如上，但是遞歸畢竟有缺陷，就是需要不斷開辟棧幀，當數據量超過10w以上時就會有棧溢出的風險。
并且遞歸類似二叉樹的結構越往下遞歸調用越多，棧幀翻倍開辟，因此我們還可以去優化一下，就是當遞歸到左右區間比較小時，我們去控制剩下的排序用別的排序來代替它。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//優化：void quicksort(int* a, int left, int right){ if (left >= right) return; if (right - left + 1 < 10) { //小區間優化 insertsort(a + left , right - left + 1); } else { int keyi = partion3(a, left, right); quicksort(a, left, keyi - 1); quicksort(a, keyi + 1, right); } } |
非遞歸：
非遞歸版本就是改變了快排的框架，用一個棧和循環來代替遞歸實現。依次將左右下標入棧出棧（出棧之前排序）來模擬遞歸。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void quicksortnonr(int* a, int left, int right){ stack st;//定義一個棧 stackinit(&st);//初始化 stackpush(&st, left);//左下標入棧 stackpush(&st, right);//右下標入棧 while (stackempty(&st)!=0) { int end = stacktop(&st);//獲取棧頂元素即后入棧的右下標 stackpop(&st);//出棧 int begin = stacktop(&st);//獲取棧頂元素即先入棧的左下標 stackpop(&st);//出棧 int keyi = partion3(a, begin, end); if (keyi + 1 < end)//相當于遞歸左半部分 { stackpush(&st, keyi + 1); stackpush(&st, right); } if (keyi - 1 > begin)//相當于遞歸右半部分 { stackpush(&st, keyi - 1); stackpush(&st, begin); } }} |
七、歸并排序
時間復雜度
最壞：-----------o(nlogn)
最好：-----------o(nlogn)
平均：-----------o(nlogn)
空間復雜度
o(n)
穩定性：穩定
基本思想：
歸并排序（merge-sort）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（divide andconquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 動圖演示：
歸并的思想就是把先假設數組分成兩個有序，對其進行篩選排序，如上圖：
但是問題來了我們怎么保證數組是有序的？因此就要求我們從小區間開始對數組歸并排序，對于上圖中的數據，先對開始3和3歸并，小的先進入到tmp數組，因此前兩個就是有序，再對，5和6歸并，5,6有序后，在歸并3，3，5，6……以此類推
代碼實現
遞歸寫法
框架：
|
1
2
3
4
5
6
7
8
9
10
11
|
void mergesort(int* a,int n){ int* tmp = (int*)malloc(sizeof(int) * n);//開辟n個大小數組 if (tmp == null) { exit(-1); } _mergesort(a, 0, n - 1, tmp);//進行歸并操作 free(tmp); tmp = null;} |
歸并排序：
運用遞歸先不斷縮小偏序區間，在遞歸層層退出時一遍退出，一邊對不斷回大的區間歸并排序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
void _mergesort(int* a, int left, int right,int* tmp){ if (left >= right) { return;//遞歸截止條件left >= right區間中數的個數<=0個 } int mid = left + (right - left) / 2;//取中 _mergesort(a, left, mid, tmp);//對左區間遞歸 _mergesort(a, mid+1, right, tmp);//對右區間遞歸 int begin1 = left, end1 = mid;//左區間 int begin2 = mid+1, end2 = right;//右區間 int i = left; 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++]; } for (size_t i = left; i <= right; i++) { a[i] = tmp[i];//把排好序[left,right]的tmp賦值給原數組 }} |
非遞歸
非遞歸的不同就是需要手動控制區間大小，也就是不斷2倍擴大區間歸并。
但是還需要注意就是當下標是奇數，無法分成整數個組的時候，需要考慮剩余的數，以及是否越界的問題
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
void mergesortnonr(int* a, int n){ int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == null) { exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { //[i][i+gap-1] [i+gap][i+2*gap-1] int begin1 = i, end1 = i + gap-1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int index = i; if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } while (begin1<=end1 && begin2<=end2) { if (a[begin1] <= a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //控制越界問題三種情況 if (end1 >= n) { end1 = n - 1; } if (end1 >= n) { end1 = n - 1; } if (end1 >= n) { end1 = n - 1; } for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = null;} |
八、計數排序
時間復雜度
最壞：-----------o(max(n,范圍))
最好：-----------o(max(n,范圍))
平均：-----------o(max(n,范圍))
空間復雜度
o(范圍)
穩定性：不穩定
思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。 操作步驟：
- 統計相同元素出現次數
- 根據統計的結果將序列回收到原來的序列中
動圖如下：
類似桶排序的思想，如上圖，先開辟數組統計數組中某一個數出現的次數，比如2出現1次，3出現兩次，那么我們直接按順序讀入開辟的數組，在原數組寫1一個2，兩個3以此類推……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
void countsort(int* a, int n){ int max=a[0], min= a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); memset(count, 0, sizeof(int)*range); for (int i = 0; i < n; i++) { count[a[i] - min]++; } int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } }} |
計數排序的特性總結：
計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限。
九、各種排序總結比較
1. 復雜度總結
2. 性質分類
以上就是c語言 八大排序算法的過程圖解及實現代碼的詳細內容，更多關于c語言八大排序算法的資料請關注服務器之家其它相關文章！
原文鏈接：https://blog.csdn.net/weixin_51484780/article/details/121628023
