06-排序

排序

1. 排序的概念及其應用

1.1 排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

內部排序：數據元素全部放在內存中的排序。

外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

1.2 常見的排序算法

在這里插入圖片描述

2. 常見排序算法的實現

在下面的算法中會頻繁使用到比較和交換，這里把這兩個功能實現以下，下面直接調用。

// 設置一個比較函數，調整升序降序時只需要修改這個函數即可
bool Com(int a, int b)
{return a < b;// <為升序，>為降序
}// 交換函數
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

2.1 插入排序

2.1.1 基本思想

思想：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

類似于打撲克牌時，碼牌的過程。

在這里插入圖片描述

2.1.2 直接插入排序

當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。

// 插入排序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int tmp = a[i];int pos = i - 1;while (pos >= 0)if (!Com(a[pos], tmp))a[pos + 1] = a[pos--];elsebreak;a[pos + 1] = tmp;}
}

直接插入排序的特性總結：

元素集合越接近有序，直接插入排序算法的時間效率越高
時間復雜度： $O(N^2)$
空間復雜度： $O (1)$
穩定性：穩定

2.1.3 希爾排序（縮小增量排序）

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數gap，把待排序文件中所有記錄分成若干個組，所有距離相同的記錄分在同一組內，并對每一組內的記錄進行排序。然后減小gap，我們這里使gap=gap/3+1（縮小gap時，必須保證最后的gap為1），重復上述分組和排序的工作。當gap=1時，所有記錄在統一組內排好序。

// 希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;// 對每個分組進行直接插入排序for (int i = gap; i < n; i++){int tmp = a[i];int pos = i - gap;while (pos >= 0)if (!Com(a[pos], tmp)){a[pos + gap] = a[pos];pos -= gap;}elsebreak;a[pos + gap] = tmp;}}
}

希爾排序的特性總結：

希爾排序是對直接插入排序的優化。
當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定。

數據結構(C語言版)》— 嚴蔚敏

《數據結構-用面相對象方法與C++描述》— 殷人昆

我們這里的gap是按照Knuth提出的方式進行取值的，而且Knuth進行了大量的試驗統計，我們暫時就按照： $O(N^{1.25})-O(1.6*N^{1.25})$ 來算。
穩定性：不穩定

2.2選擇排序

2.2.1 基本思想

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

2.2.2 直接選擇排序

在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

// 選擇排序
void SelectSort(int* a, int n)
{for (int i = n - 1; i > 0; i--){int pos = i;for (int j = 0; j < i; j++)if (Com(a[pos], a[j]))pos = j;Swap(&a[i], &a[pos]);}
}

優化

// 選擇排序優化，兩端同時進行排序
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = end;for (int i = begin; i <= end; i++){if (Com(a[i], a[mini]))mini = i;if (Com(a[maxi], a[i]))maxi = i;}Swap(&a[begin], &a[mini]);if (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);begin++;end--;}
}

直接選擇排序的特性總結：

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
時間復雜度： $O(N^2)$
空間復雜度： $O (1)$
穩定性：不穩定

2.2.3 堆排序

利用堆這個數據結構進行排序，是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。

（關于數據結構—堆，詳見05-二叉樹-CSDN博客）

// 堆---向下調整
void AdjustDwon(int* a, int n, int root)
{int child = root * 2 + 1;while (child < n){if (child + 1 < n && Com(a[child], a[child + 1]))child++;if (!Com(a[root], a[child])) break;Swap(&a[root], &a[child]);root = child;child = root * 2 + 1;}
}// 堆排序
void HeapSort(int* a, int n)
{for (int i = n / 2; i >= 0; i--)AdjustDwon(a, n, i);for (int i = n - 1; i > 0; i--){Swap(&a[0], &a[i]);AdjustDwon(a, i, 0);}
}

直接選擇排序的特性總結：

堆排序使用堆來選數，效率就高了很多。
時間復雜度： $O (N ? l o g N)$
空間復雜度： $O (1)$
穩定性：不穩定

2.3 交換排序

2.3.1 基本思想

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

2.3.2 冒泡排序

很基礎的算法，這里不過多介紹。（詳細介紹：012-C語言指針（2）-CSDN博客）

// 冒泡排序
void BubbleSort(int* a, int n)
{for (int i = n - 1; i > 0; i--){bool flag = true;for (int j = 0; j < i; j++)if (Com(a[j + 1], a[j])){flag = false;Swap(&a[j + 1], &a[j]);}if (flag) break;}
}

冒泡排序的特性總結：

冒泡排序是一種非常容易理解的排序
時間復雜度： $O(N^2)$
空間復雜度： $O (1)$
穩定性：穩定

2.3.3 快速排序

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

// 假設按照升序對array數組中[left, right)區間中的元素進行排序
void QuickSort(int array[], int left, int right)
{if (right - left <= 1)return;// 按照基準值對array數組的 [left, right)區間中的元素進行劃分int div = partion(array, left, right);// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)// 遞歸排[left, div)QuickSort(array, left, div);// 遞歸排[div+1, right)QuickSort(array, div + 1, right);
}

上述為快速排序遞歸實現的主框架，發現與二叉樹前序遍歷規則非常像，在寫遞歸框架時可想想二叉樹前序遍歷規則即可快速寫出來，后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。

關于選擇基準值：

為了提高效率，選擇基準值時要盡量避免選擇到最值，所以這里實現一個選擇函數。

// 篩選key
int GetMidi(int* a, int begin, int end)
{int midi = (end + begin) / 2;if (a[begin] > a[end]){if (a[midi] > a[end]){if (a[begin] > a[midi])return midi;elsereturn begin;}elsereturn end;}else{if (a[begin] > a[midi])return begin;else{if (a[midi] > a[end])return end;elsereturn midi;}}
}

將區間按照基準值劃分為左右兩半部分的常見方式有三種（這里以升序序列為例）：

hoare版本

對于一個待排序序列，選擇其中任意一個值作為基準值key，把這個基準值拿出來，與序列中的第一個元素交換位置，剩余的序列中，使用兩個指針，分別指向序列的頭+1（因為現在第一個位置存放了基準值key）和尾（開區間），右指針一直–，直到碰到<key的值，左指針一直++，直到碰到>key的值然后停下，然后將左指針和右指針指向的值交換，再重復上述操作，直到兩個指針相遇，此時兩個指針都指向<=key的值（這里不做證明，注意上面指針移動的順序），此時將基準值和這個值進行交換，序列就分成了兩段。
```
int PartSort1(int* a, int begin, int end)// 基礎法
{int midi = GetMidi(a, begin, end);// 優化，排除最值做key，提升排序效率Swap(&a[begin], &a[midi]);int keyi = begin;int left = begin;int right = end;while (left < right){while (left < right && !Com(a[right], a[keyi]))right--;while (left < right && !Com(a[keyi], a[left]))left++;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}
```
挖坑法

對于一個待排序序列，選擇一個基準值，將這個基準值和序列第一個值進行交換，然后將這個基準值key記錄下來，將左指針和右指針分別指向第一個元素和最后一個元素，此時第一個元素的位置是一個“坑”，因為這里的值已經被我們提取出來了，此時判斷右指針指向的元素，只要該元素>=key，右指針–，直到碰見小于key的值，將這個值放到左指針指向的“坑”，此時右指針指向一個“坑”，判斷左指針指向的元素，只要該元素<=key左指針++，直到碰見大于key的值，將該值放到右指針指向的“坑”中，反復上面過程，直到左右指針相遇，此時它們共同指向一個坑，將我們記錄的基準值放到這個坑中即可。
```
int PartSort2(int* a, int begin, int end)// 挖坑法
{int midi = GetMidi(a, begin, end);// 優化，排除最值做key，提升排序效率Swap(&a[begin], &a[midi]);int key = a[begin];int left = begin;int right = end;while (left < right){while (right > left && !Com(a[right], key))right--;a[left] = a[right];while (right > left && !Com(key, a[left]))left++;a[right] = a[left];}a[left] = key;return left;
}
```
前后指針版本

同樣，對于一個待排序序列，選一個基準值key，放在第一個位置，此時我們需要兩個指針prev和cur，分別指向第一個元素和第二個元素，cur一直++，直到碰到；小于key的元素，將這個元素和prev+1位置的元素交換位置，prev++，然后重復上述操作，直到cur碰到end，交換prev和begin位置（key）的元素，單趟排序結束，在這個過程中，(begin,prev]代表小于等于key的序列，(prev,cur)代表大于等于key的序列，[cur,end)代表待排序序列。
```
int PartSort3(int* a, int begin, int end)// 雙指針法
{int midi = GetMidi(a, begin, end);// 優化，排除最值做key，提升排序效率Swap(&a[begin], &a[midi]);int keyi = begin;int cur = begin + 1;int prev = begin;while (cur <= end){if (Com(a[cur], a[keyi]) && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[keyi], &a[prev]);return prev;
}
```

快速排序主體

// 快速排序 - 遞歸實現
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;// 當待排序序列較小時，可以直接使用插入排序，可以有效減少遞歸的深度。當然不加也是可以的。if (end - begin + 1 <= 10)// 小區間優化，減少遞歸深度，防止棧溢出InsertSort(a + begin, end - begin + 1);else{//三種方法實現單趟排序,此處任選一種單趟排序即可//int keyi = PartSort1(a, begin, end);//常規//int keyi = PartSort2(a, begin, end);//挖坑int keyi = PartSort3(a, begin, end);//雙指針QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

上面實現的是遞歸的快速排序，我們還可以使用迭代的方法來實現，但這需要借助棧的數據結構（關于棧，參考：04-棧和隊列-CSDN博客，在下面的實現中，使用這篇文章中實現的棧的接口）。

// 快速排序 - 非遞歸實現（用棧的數據結構實現）
void QuickSortNonR(int* a, int begin, int end)
{Stack ST;StackInit(&ST);StackPush(&ST, end);StackPush(&ST, begin);while (!StackEmpty(&ST)){int left = StackTop(&ST);StackPop(&ST);int right = StackTop(&ST);StackPop(&ST);//進行單趟排序，任選一種即可//int keyi = PartSort1(a, left, right);//常規//int keyi = PartSort2(a, left, right);//挖坑int keyi = PartSort3(a, left, right);//雙指針if (right > keyi + 1){StackPush(&ST, right);StackPush(&ST, keyi + 1);}if (left < keyi - 1){StackPush(&ST, keyi - 1);StackPush(&ST, left);}}StackDestroy(&ST);
}

快速排序的特性總結：

快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
時間復雜度： $O (N ? l o g N)$
空間復雜度： $O (l o g N)$
穩定性：不穩定

2.4 歸并排序

2.4.1 基本思想

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

在這里插入圖片描述

2.4.2 具體實現

遞歸實現

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int midi = (end + begin) / 2;_MergeSort(a, begin, midi, tmp);_MergeSort(a, midi + 1, end, tmp);int begin1 = begin;int begin2 = midi + 1;int i = begin;while (i <= end){if (Com(a[begin1], a[begin2])){tmp[i] = a[begin1];begin1++;}else{tmp[i] = a[begin2];begin2++;}i++;if (begin1 > midi || begin2 > end)break;}if (begin1 > midi)while (i <= end)tmp[i++] = a[begin2++];elsewhile (i <= end)tmp[i++] = a[begin1++];memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}// 歸并排序 - 遞歸實現
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc error");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

迭代實現

// 歸并排序 - 非遞歸實現
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc error");exit(-1);}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;if (end1 >= n || begin2 >= n)break;if (end2 >= n)end2 = n - 1;int j = begin1;while (j <= end2){if (Com(a[begin2], a[begin1]))tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];if (begin1 > end1 || begin2 > end2)break;}while (begin1 <= end1)tmp[j++] = a[begin1++];while (begin2 <= end2)tmp[j++] = a[begin2++];memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}
}

歸并排序的特性總結：

歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
時間復雜度： $O (N ? l o g N)$
空間復雜度： $O (N)$
穩定性：穩定

2.5 非比較排序（計數排序）

2.5.1 基本思想

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

統計相同元素出現次數
根據統計的結果將序列回收到原來的序列中

在這里插入圖片描述

2.5.2 具體實現

// 計數排序 - 效率奇高，適用于數據范圍較小時
void CountSort(int* a, int n)
{int max = a[0];int 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* count = (int*)calloc(max - min + 1, sizeof(int));if (count == NULL){perror("calloc error");exit(-1);}for (int i = 0; i < n; i++)count[a[i] - min]++;int i = 0;int j = 0;while (i <= max - min){if (count[i]){a[j++] = i + min;count[i]--;}elsei++;}free(count);
}