算法：六種比較排序算法
本文是本人讀過《算法導論》之后所寫，C代碼實現是我盡量參照偽代碼所寫，如有錯誤，敬請指正。
*：所有排序算法默認從小到大排序,偽代碼數組的首元素為A[1], 數組長度為n
一、冒泡排序
冒泡排序應該是最簡單的比較排序了，排序原理就是重復遍歷數組，每次比較相鄰的兩個元素，如果前一個元素大于后一個元素，則交換數組兩個元素的位置。這樣每遍歷一次，最大的元素就會下沉到數組最底部，重復遍歷n-1次，所有元素就都已排好序了。
偽代碼：
1. for i = 1 to n-1
2. for j = 1 to n-i
3. if A[j] > A[j+1]
4. exchange A[j] with A[j+1]
偽代碼講解：
第一行控制遍歷輪數；
第二行控制需要比較的數組元素下標范圍；
第三四行，當相鄰的兩個元素不滿足比較條件時，交換兩個元素的位置
C代碼：
/*Author:Terry Zhang*/ #include <stdio.h> #include <stdlib.h> int main(void) { size_t n = 0; scanf_s("%d", &n); int *p = (int *)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d", p + i); } int * p0 = p; for (size_t i = 0; i < n-1; i++) { for (size_t j = 0; j < n-i-1; j++) { int t = 0; if (p[j] > p[j + 1]) { t = p[j]; p[j] = p[j + 1]; p[j + 1] = t; } } } p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ", *(p0++)); } printf("\n"); free(p); return 0; }
二、選擇排序
選擇排序是一種簡單直觀的排序算法，排序思路是，第一次通過比較選出數組中最小的元素放在數組的起始位置，接著比較剩下的元素選出最小的元素放在已經排好序的序列后面，以此類推，直到所有元素排序完畢。
偽代碼：
1. for i=1 to n-1
2. min = i;
3. for j=i+1 to n
4. if A[j] < A[min]
5. min = j;
6. if min != i
7. exchange A[i] with A[min]
偽代碼講解：
第一行控制遍歷輪數；
第二行將最小值下標設置為當前未排序數組下標的第一個；
第四五行，如果發現比當前最小值小的元素，則將min更新；
第六七行，如果最小值下標和當前未排序數組下標的第一個（j）不等，則交換A[i]和A[min],即將最小值移動到已排序數組末尾
C代碼：
#include <stdio.h> #include <stdlib.h> int main(void) { size_t n = 0; scanf_s("%d", &n); int *p = (int *)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d", p + i); } for (size_t j = 0; j < n - 1; j++) { int min = j; for (size_t k = j + 1; k < n; k++) { if (p[k] <= p[min]) min = k; } if (min != j) { int t = p[j]; p[j] = p[min]; p[min] = t; } } int * p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ", *(p0++)); } printf("\n"); free(p); return 0; }
三、插入排序
插入排序的排序思想是，通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
偽代碼：
1. for i = 2 to n
2. key = A[i];
3. j = i - 1;
4. while j >= 1 and A[j] > key
5. A[j+1] = A[j];
6. j = j - 1;
7. A[j + 1] = key;
偽代碼講解：
第一行控制循環輪數；
第二行key為當前需要插入的元素；
第四到六行，將比key大的元素依次后移，直到遇到第一個不大于key的元素跳出循環；
第七行將需要插入的元素key插入到在已排序好的序列中應有的位置
C代碼：
/*Author：Terry Zhang*/ #include<stdio.h> #include<stdlib.h> int main(void) { //輸入n個數 size_t n = 0; scanf_s("%d",&n); int *p; p = (int *)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d", p + i); } //排序 int key = 0, i = 0; for (size_t j = 1; j < n; j++) { key = p[j]; i = j - 1; while (i >= 0 && p[i] > key) { p[i + 1] = p[i]; i--; } p[i + 1] = key; } //格式化輸出 int *p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ",*p0++); } printf("\n"); free(p); return 0; }
四、堆排序
堆排序像插入排序而不像歸并排序（見第五種排序），它是一種原址排序算法（元素的相對位置排序前后不發生變化）；像歸并排序而不像插入排序，堆排序運行時間為O（nlgn). (二叉)堆數據結構是一種數據對象，它可以被視為一棵近似的完全二叉樹，樹中每一個元素分別對應數組中的一個元素，且從左到右依次排列。這樣給定一個節點的下標i,我們很容易計算得到它的父節點、左孩子和右孩子的下標。在排序算法中我們使用最大堆（滿足A[Parent(i)] >= A[i]），最小堆用于構造優先隊列。
Parent（i）
return 
Left(i)
return 2i
Right
return 2i+1
下面我們介紹排序算法中需要用到的三個函數
1. ManHeapify過程：時間復雜度為O（lgn）, 它是維護最大堆性質的關鍵
2. BuildMaxHeap過程：它具有線性時間復雜度，功能是從無序的數組中構造一個最大堆
3.HeapSort排序過程：時間復雜度為O(nlgn)，功能是對一個數組進行原址排序
維護堆的性質：
我們通過MaxHeapify函數來維護堆的性質，我們假定根節點為Left（i）和Right（i）的二叉樹都是最大堆，此時A[i]可能小于它的孩子，此函數的目的就是讓A[i]在最大堆中“逐級下降”，從而使得以下標i為根節點的子樹重新遵循最大堆的性質。
偽代碼：
MaxHeapify(A,i)
1. l = Left(i)
2. r = Right(i)
3. if l <= n and A[l] > A[i]
4. largest = l
5. else largest = i
6. if r <= n and A[r] > A[largest]
7. largest = r
8. if largest != i
9. exchange A[i] with A[largest]
10 MaxHeapify(A,largest)
偽代碼解釋：
第一二行獲取根節點i的左右孩子的下標；
第三行到七行比較根節點與左右孩子的大小，更新largest為三者中最大元素的下標；
第八九行，如果根節點largest！= i，即根節點小于某個孩子，則交換根節點與A[largest]的位置；
第十行，重復1~9
建堆：
我們可以利用自底向上的方法利用過程Maxheapify把一個大小為n的數組轉換為最大堆,通過計算我們知道，A[n/2 + 1] to A[n]都是葉結點，而每個葉節點可以看成是只有一個元素的堆。該過程對樹中其他結點都調用一次MaxHeapify從范圍完成建堆過程
偽代碼：
BuildMaxHeap(A)
1. for i = n/2 downto 1
2. MaxHeapify(A,i)
堆排序算法：
我們已經直到最大堆的一個最重要的性質就是根節點永遠大于等于子結點，也就是說最大的元素永遠在根節點A[1]處，我們可以利用這一性質對數組進行排序。排序的方法是交換A[1]和A[n]的位置，之后去掉結點n，維持堆的性質，之后重復此過程，最終完成排序。
偽代碼：
HeapSort（A）
1. BuildMaxHeap(A)
2. for i = A.length downto 2
3. exchange A[1] with A[i]
4. A.heap_size = A.heap_size - 1
5. MaxHeapify(A,1)
完整的C代碼如下：
/*Authority:Terry Zhang*/ #include <stdio.h> #include <stdlib.h> int main() { size_t n = 0; scanf_s("%d", &n); int *p = (int *)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d", p + i); } void BuildMaxHeap(int *A, int n); void HeapSort(int *A, int n); HeapSort(p, n); int *p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ", *p0++); } free(p); return 0; } //maintain max heap function void MaxHeapify(int *A, int n, int i) { int Left(int i); int Right(int i); void Swap(int *A, int i, int j); int l = Left(i); //get the subscript of its left child int r = Right(i); //get the subscript of its right child int largest; if (l < n && A[l] > A[i]) //n = A.heap_size largest = l; else largest = i; if (r < n && A[r] > A[largest]) //n = A.heap_size largest = r; if (largest != i) { Swap(A, i, largest); MaxHeapify(A, n, largest); } } //build max heap void BuildMaxHeap(int *A, int n) { for (int i = n / 2 - 1; i >= 0; i--) { MaxHeapify(A, n, i); } } //heap sort void HeapSort(int *A,int n) { BuildMaxHeap(A, n); void Swap(int *A, int i, int j); for (int i = n - 1; i >= 1; i--) //n -1 to 1 { Swap(A, 0, i); MaxHeapify(A, i, 0); } } //return the subscript of i's left child int Left(int i) { return (i <<= 1) + 1; } //return the subscipts of i's right child int Right(int i) { return (i <<= 1) + 2; } void Swap(int *A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; }
五、歸并排序
歸并排序是一種使用分治法（divide and conquer）的排序算法，分治法的思想是將原有的一個規模比較大的問題，分解成若干個規模較小但又類似于原問題的子問題，然后求解子問題，再合并子問題的解來建立原問題的解。
分治模式在每層遞歸中都有三個步驟：
1. 分解原問題為若干子問題，這些子問題都是原問題規模較小的實例
2. 解決這些子問題。遞歸地求解子問題，當子問題規模足夠小時則直接求解
3. 合并這些子問題的解形成原問題的解
歸并排序完全符合分治模式
1. 分解：待排序的n個元素的序列成各具n/2個元素的兩個子序列
2. 解決：使用歸并排序遞歸的排序兩個子序列
3. 合并：合并兩個已排好的子序列產生已排序的整個序列
當待排序的序列長度為1時，遞歸“開始回升”，因為長度為1的序列可以被認為是已經排好序的了。
歸并排序中最關鍵的步驟是合并，我們通過一個輔助過程Merge（A,p,q,r）完成，p,q,r為數組下標，滿足p<=q<r。我們假定A[p,q]和A[q+1,r]都是已經排好序的，這樣通過Merge過程合并兩個子數組形成一個排好序的新數組A[p,r]來取代原有的數組。我們可以以玩撲克牌為例，假設桌子上有兩堆牌面朝上的牌，每堆都是已經排好序的，最小的牌在最上面。合并操作的過程為，每次比較最上面的兩張牌，將較小的牌牌面朝下放在桌子上，當一堆牌為空時，將另一堆牌直接放到輸出堆中則完成了整個合并過程。為了避免每次都要檢查兩堆牌是否為空，我們在每堆牌的底部放置一個“哨兵牌”，我們以《無窮大》為哨兵值，哨兵牌不小于任何牌。下面的偽代碼實現了這一思想：
偽代碼：
Merge(A,p,q,r)
1. n1 = q - p + 1
2. n2 = r - q
3. Let L[1..n1+1] and R[1..n2+1] be new arrays
4. for i = 1 to n1
5. L[i] = A[p+i-1]
6. for j = 1 to n2
7. R[j] = A[q+j]
8. L[n1+1] = 無窮大
9. R[n2+1] = 無窮大
10. i = 1
11. j = 1
12. for k = p to r
13. if L[i] <= R[j]
14. A[k] = L[i]
15. i = i + 1
16. else A[k] = R[j]
17. j = j + 1
偽代碼解釋：
第一二行計算兩個子數組的長度；
第三行創建兩個新數組L，R，并且分別創建一個額外位置來存取哨兵；
第四行到第七行將兩個子數組拷貝到兩個新數組L,R中；
第八九行設置哨兵值；
第十二到十七行完成合并過程
完成這個輔助過程，我們就會很容易寫出歸并排序算法的偽代碼：
MergeSort（A,p,r）
1. if p < r
2. q = (p+r)/2
3. MergeSort(A,p,q)
4. MergeSort(A,q+1,r)
5. Merge(A,p,q,r)
完整C代碼如下：
/*Author：Terry Zhang*/ #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <math.h> void Merge(int *A, size_t p, size_t q, size_t r); void MergeSort(int *A, size_t p, size_t r); int main(void) { size_t n; scanf_s("%d", &n); int *p = (int*)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d",p + i); } MergeSort(p, 0, n - 1); //output int *p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ", *p0++); } printf("\n"); //free free(p); return 0; } //Merge Sort void MergeSort(int *A, size_t p, size_t r) { if (p < r) { size_t q = (p + r) / 2; MergeSort(A, p, q); MergeSort(A, q + 1, r); Merge(A, p, q, r); } } //auxiliary procedure void Merge(int *A, size_t p, size_t q, size_t r) { size_t n1 = q - p + 1; size_t n2 = r - q; size_t i = 0; size_t j = 0; int *L = (int *)calloc(n1 + 1, sizeof(int)); int *R = (int *)calloc(n2 + 1, sizeof(int)); for (i = 0; i < n1; i++) { L[i] = A[p+i]; } for (j = 0; j < n2; j++) { R[j] = A[q+1+j]; } L[i] = INT_MAX; //not L[i+1] R[j] = INT_MAX; i = 0; j = 0; for (size_t k = p; k <= r; k++) { if (L[i] <= R[j]) A[k] = L[i++]; else A[k] = R[j++]; } free(L); free(R); }
六、快速排序
快速排序，名副其實，它是最廣泛使用的一種快速排序算法。快速排序最壞情況下的時間復雜度和插入排序一樣，但是它的平均時間復雜度卻和歸并排序一樣。具體的原因可以參見《算法導論》，書中有詳細的數學證明。
快速排序同歸并排序一樣，也是采用了分治思想。同樣，我們以分治思想的三個必要步驟來解釋這個算法：
1. 分解：數組A[p...r] 被分解成兩個子數組A[p...q-1]和A[q+1...r]，使得前一個數組中的每一個元素都小于等于A[q]，后一個數組中的每一個元素都大于等于A[q]，其中計算下標q也是劃分過程的一部分
2. 解決：通過遞歸調用快速排序，對兩個子數組進行排序
3. 合并： 因為子數組都是排好序的，所以不需要合并操作。
實質上，快速排序在劃分的過程中也是在排序的過程中，這一點是它不同于歸并排序的地方，也是不需要合并的原因。
快速排序的偽代碼：
QuikSort(A,p,r)
1. if p < r
2. q = Partition(A,p,r)
3. QuickSort(A,p,q-1)
4. QuickSort(A,q+1,r)
由此可將，數組劃分是快速排序算法最關鍵的部分
數組劃分的偽代碼：
Partition(A,p,r)
1. key = A[r]
2. i = p-1;
3. for j = p to r-1
4. if A[j] <= key
5. i = i + 1
6. exchange A[i] with A[j]
7. exchange A[i+1] with A[r]
8. return i + 1
偽代碼講解：
第一行我們設置數組最后一個元素為劃分的主元key;
第二行初始化變量i，i在劃分過程中用來表示比key小的元素應該放置的位置下標，即數組前面的部分;
第三到六行，j用來遍歷數組中的元素，當發現比key小的元素A[j]時就將其依次放到數組前面部分，即與A[i] 交換，這樣完成后數組前面部分都是小于等于key的元素；
第七行，將A[r]即key交換到所有小于等于key的元素的后面，這樣整個數組就被key劃分了一次，key也就恰好被放置到了它最終排序后應該在的位置；
第八行，返回劃分位置下標
完整C代碼如下：
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { size_t n; scanf_s("%d", &n); int *p = (int *)calloc(n, sizeof(int)); for (size_t i = 0; i < n; i++) { scanf_s("%d", p + i); } void QuickSort(int A[], int p, int r); QuickSort(p, 0, n-1); //output int *p0 = p; for (size_t i = 0; i < n; i++) { printf("%d ", *p0++); } printf("\n"); free(p); return 0; } void QuickSort(int A[], int p, int r) { int Partition(int A[], int p, int r); if (p < r) { int q = Partition(A, p, r); QuickSort(A, p, q - 1); //q-1 not q QuickSort(A, q + 1, r); } } void swap(int v[], int i, int j) { int temp; temp = v[j]; v[j] = v[i]; v[i] = temp; } int Partition(int A[], int p, int r) { int x = A[r]; int i = p - 1; for (size_t j = p; j <= r-1; j++) { if (A[j] <= x) { i++; swap(A, i, j); } } swap(A, i + 1, r); return i + 1; }
以上我們的前提假設是輸入數據的所有排列都是等概率的，所以我們每次選擇數組或者子數組的最后一個元素為主元key，但實際情況這一假設并不總是成立，所以我們要考慮隨機選取主元key，隨機性的引入使得快讀排序對所有的可能輸入都會得到一個較好的期望性能。這就是快速排序的隨機化版本。
偽代碼很簡單：
RandomPartition（A,p,r）
1. i= Random（p,r）
2. exchange A[r] with A[r]
3. return Partition(A,p,r)
隨機劃分的C代碼如下：
int Randomized_Partition(int A[], int p, int r) { srand((unsigned)time(NULL)); int t = rand() % (r - p) + p; swap(A, t, r); return Partition(A, p, r); }
浙公網安備 33010602011771號