算法－七大排序算法詳細介紹

算法 FLAG Java從算法到架構 2019-06-27

排序的相關概念

排序的分類

根據在排序過程中帶排序的記錄是否全部被放置在內存中，排序分為：
內排序
外排序

1.內排序

內排序是在排序整個過程中，帶排序的所有記錄全部放置在內存中。

影響內排序的主要因素

時間性能。
(主要受比較和移動兩種操作的影響）
輔助空間。
算法的複雜性。

內排序的分類

根據排序過程中藉助的主要操作，內排序分為：

插入排序
交換排序
選擇排序
歸併排序

2.外排序

外排序是由於排序的記錄個數太多，不能同時放置在內存中，整個排序過程需要在內外存之間多次交換數據才能進行。

按照算法的複雜度分類

簡單算法：
冒泡排序、簡單選擇排序、直接插入排序。
複雜排序：
希爾排序、堆排序、歸併排序、快速排序。

一、冒泡排序算法

因為在冒泡排序中要用到順序表結構和數組兩元素的交換，先把這些寫成函數

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
typedef struct {
 
 int r[MAXSIZE + 1];
 int length;
}SqList;
void swap(SqList *L, int i, int j){
 int temp = L->r[i];
 L->r[i] = L->r[j];
 L->r[j] = temp;
}

1.1 冒泡排序的初級版實現

冒泡排序（Bubble Sort）是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

void BubblSort0(SqList *L){
 int i,j;
 
 for (i = 1; i < L->length; i++)
 for (j = i+1; j <= L->length; j++)
 if (L->r[i] > L->r[j])
 swap(L, i, j);
}

對於這段代碼，是最簡單的冒泡，其實就是最簡單的交換排序而已。它的思路就是讓每一個關鍵字，都和它後面的每一個關鍵字比較，如果大則交換，這樣第一位置的關鍵字在第一次循環後一定變成最小值。

假設我們待排序的關鍵字序列是{9，1，5，8，3，7，4，6，2}

當i = 1時，9與1交換後，在第一位置的1與後面的關鍵字比較都小，因此它就只最小值。
當i = 2時，第二位置先後由9換成5，換成3，換成2，完成了第二小的數字交換。
後面數字依次比較和交換，得到最終結果。

1.2 冒泡排序的實現

對於上面的算法，代碼雖然簡單易懂，但是效率非常低。可以改進成接下來的代碼

void BubbleSort(SqList *L){
 int i,j;
 for (i = 1; i < L->length; i++)
 for (j = L->length - 1; j >= i; j--)
 if (L->r[j] > L->r[j+1])
 swap(L, j, j+1);
}

代碼解釋

假設我們待排序的關鍵字序列是{9，1，5，8，3，7，4，6，2}

當i = 1時，變量j由8反向循環到1，逐個比較，將較小值交換到前面，直到最後找到最小值放置在了第1的位置。
當i = 1、 j = 8時，6 > 2 ，因此交換了它們的位置，j = 7時，4 > 2，所以交換......直到j = 2時，因為 1 < 2，所以不交換。
j = 1 時，9 > 1，交換，最終得到最小值1放置第一的位置。
在不斷循環的過程中，除了將關鍵字1放到第一的位置，還將關鍵字2從第九位置提到了第三的位置，顯然比前面的算法有進步。
當i = 2時，變量j由8反向循環到2，逐個比較，在將關鍵字2交換到第二位置的同時，也將關鍵字4和3有所提升。

1.3 冒泡排序的優化

在排序的過程中，增加一個標記變量flag來記錄位置是否發生了變化
如果沒有發生交換，說明數組已經有序了。

void BubbleSort1(SqList *L){
 int i,j;
 
 int flag = TRUE;
 for (i = 1; i < L->length && flag; i++) {
 flag = FALSE;
 for (j = L->length - 1; j >= i; j--) {
 if (L->r[j] > L->r[j+1]) {
 swap(L, j, j+1);
 flag = TRUE;
 }
 }
 }
}

測試

#define N 9
int main(int argc, const char * argv[]) {
 
 int i;
 int d[N] = {9,1,5,8,3,7,4,6,2};
 
 SqList l0;
 for (i = 0; i < N; i++)
 l0.r[i+1] = d[i];
 l0.length = N;
 
 printf("排序前：\n");
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("\n");
 
 printf("1.0 初級冒泡排序結果:\n");
 BubblSort0(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("\n");
 
 printf("1.1 冒泡排序結果:\n");
 BubbleSort(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("\n");
 printf("1.2 優化後冒泡排序結果:\n");
 BubbleSort1(&l0);
 for (i = 0; i < l0.length; i++) {
 printf("%d ", l0.r[i+1]);
 }
 printf("\n");
 return 0;
}

測試結果

二、簡單選擇排序

簡單選擇排序法(Simple Selection Sort)是通過n-i次關鍵字間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，並和第i(1<=i<=n)個記錄交換。

簡單選擇排序法的工作原理是：每一次從無序組的數據元素中選出最小（或最大）的一個元素，存放在無序組的起始位置，無序組元素減少，有序組元素增加，直到全部待排序的數據元素排完。

void SelectSort(SqList *L){
 int i, j, min;
 for (i = 1; i < L->length; i++) {
 min = i;
 for (j = i + 1; j <= L->length; j++) {
 if (L->r[min] > L->r[j])
 min = j;
 }
 
 if (i != min) 
 swap(L, i, min);
 }
}

代碼說明

簡單選擇排序相對簡單，交換移動數據的次數相當少，節約時間。
簡單選擇排序的時間複雜度為O(n^2)。

三、直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄增1的有序表。

直接插入排序的核心思想：將一個記錄插入到一個已經排序好的表中，以得到一個記錄增加1的有序表。並且它把當前元素大的記錄都往後移動，用以騰出“自己”該插入的位置。當n-1趟插入完成後該記錄就是有序序列。


void InsertSort(SqList *L){
 int i, j;
 for (i = 2; i < L->length; i++) {
 
 if (L->r[i] < L->r[i-1]) {
 
 L->r[0] = L->r[i];
 for (j = i-1; L->r[j] > L->r[0]; j++)
 L->r[j+1] = L->r[i];
 
 L->r[j+1] = L->r[0];
 }
 }
}

代碼說明

直接插入排序的時間複雜度為O(n^2)。
直接插入排序比冒泡和簡單選擇排序的性能要好一些。

四、希爾排序

希爾排序是對直接插入排序的改進：

將原本有大量記錄數的記錄進行分組。分割成若干個子序列；
對子序列分別進行直接插入排序；
當整個序列都基本有序時（注意是基本有序），再對全體記錄進行一次直接插入排序。
所謂的基本有序，就是小的關鍵字基本在前，大的基本在後面，不大不小的基本在中間，如{9,1,5,8,3,7,5,6,2}，變成{2,1,3,6,4,7,8,9}這樣就是基本有序，但是像{1,5,9,7,8,2,4,6}這樣9在第三位，2在倒數第三位就不是基本有序。
對於分割子序列，採取跳躍分割的策略：
將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內分別進行直接插入排序後得到的結果是基本有序而不是局部有序。
增量的選取非常關鍵，但是現在還是一個數學難題(迄今沒有找到一種最好的增量序列),大量研究表明，增量序列為dlta[k] = 2^(t-k+1) - 1時，可以獲得不錯的效果。

希爾排序的核心思想：希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止

void ShellSort(SqList *L){
 
 int i,j;
 
 int increment = L->length;
 
 do {
 increment = increment /3 +1;
 
 for (i = increment + 1; i < L->length; i++) {
 
 if (L->r[i] < L->r[i-increment]) {
 
 L->r[0] = L->r[i];
 
 for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment)
 L->r[j+increment] = L->r[j];
 
 L->r[j+increment] = L->r[0];
 }
 }
 } while (increment > 1);
}

代碼說明

希爾排序的時間複雜度為O(n^(3/2))，要好於直接插入排序的O(n^2);
增量的最後一個增量之必須等於1才行。
由於記錄是跳躍式的移動，所以希爾排序不是一種穩定的排序算法。

五、堆排序

堆的概念

堆是具有如下性質的完全二叉樹：

每個結點的值都大於或等於其其左右孩子結點的值，為大頂堆。
或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。
因此根節點一定是堆中所有結點最大（小）者。
如圖左邊為大頂堆，右邊為小頂堆：

左邊為大頂堆，右邊為小頂堆

堆排序算法

堆排序（Heap Sort）是利用堆（假設是大頂堆）進行排序。

堆排序的核心思想：

將待排序的序列構造成一個大頂堆。
此時，整個序列的最大值就是堆頂的根節點。
將根節點移走(其實就是將它與堆數組的末尾元素交換，此時末尾元素就是最大值)，然後將剩餘的n-1個序列重新構造成一個堆，這樣就會得到n個元素的次小值。
重複上訴操作，便能得到一個有序序列。

堆排序算法核心

如何由一個無序序列構建成一個堆
如何在輸出堆頂元素後，調整剩餘元素成一個新的堆

堆排序算法代碼實現

void HeadAdjust(SqList *L, int s, int m){
 int temp, j;
 temp = L->r[s];
 
 for (j = 2 *s; j <= m; j *= 2) {
 
 if (j < m && L->r[j] < L->r[j+1])
 j++;
 
 if (temp >= L->r[j])
 break;
 
 L->r[s] = L->r[j];
 s = j;
 }
 
 L->r[s] = temp;
}
void HeapSort(SqList *L){
 int i;
 
 for (i = L->length / 2; i>0; i--)
 HeadAdjust(L, i, L->length);
 
 for (i = L->length; i > 1; i--) {
 swap(L, 1, i);
 HeadAdjust(L, 1, i-1);
 }
}

堆排序算法代碼說明

堆排序方法HeapSort中有兩個for循環：
第一個for循環完成將現在的待排序序列構建成一個大頂堆；
第二個for循環完成逐漸將每個最大值的根節點與末尾元素交換，並且再調整其成為大頂堆。
第一個for循環中的i = L->length / 2,i從[9/2]=4開始，4->3->2->1的變化量。
（這裡賦值的原因是這些都是有孩子的結點）
構建好有孩子的結點之後，就可以從上到下、從左到右，將每個將每個非終端結點（非葉子結點）當做根節點,將其和子樹調整成大頂堆。
函數HeadAdjust的作用是將數組構建成一個大頂堆，在構建的時候利用了二叉樹的性質。
構建堆的時間複雜度為O(n)，重建堆的時間複雜度為O(nlogn)，所以總體來說堆排序的時間複雜度為O(nlogn)，性能上遠好於冒泡、簡單選擇、直接插入的時間複雜度。
在空間複雜度上，由於記錄的交換和比較是跳躍式進行的，所以堆排序是一種不穩定的排序方法。

六、歸併排序

歸併排序(Merging Sort)是利用歸併的思想實現的。2路歸併排序的核心思想如下：

假設初始序列有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸併，得到n/2個長度為2或者1的有序子序列
再兩兩歸併...如此重複，直至得到一個長度為n的有序序列為止。

6.1歸併排序的實現思路（遞歸實現）

將序列平均分成兩部分
分別對這兩部分用遞歸來歸併
將這兩部分歸併到一起

歸併排序的代碼實現（遞歸實現）

#pragma - 6.歸併排序(遞歸實現)
void Merge(int SR[], int TR[], int i, int m, int n){
 
 int j, k, l;
 
 for (j = m+1, k = i; i <= m && j <= n; k++) {
 
 if (SR[i] < SR[j])
 TR[k] = SR[i++];
 else
 TR[k] = SR[j++];
 }
 
 if (i <= m) {
 for (l=0; l <= m-i; l++)
 TR[k+l] = SR[i+l];
 }
 
 if (j <= n) {
 for (l=0; l <= n-j; l++)
 TR[k+l] = SR[j+l];
 }
}
void MSort(int SR[], int TR1[], int s, int t){
 int m;
 int TR2[MAXSIZE+1];
 
 if (s == t) {
 TR1[s] = SR[s];
 }else{
 m = (s+t)/2;
 MSort(SR, TR2, s, m);
 MSort(SR, TR2, m+1, t);
 Merge(TR2, TR1, s, m, t);
 }
}
void MergeSort(SqList *L){
 MSort(L->r, L->r, 1, L->length);
}

歸併排序的總結（遞歸實現）

歸併排序總的時間複雜度為O(nlogn)，並且這是歸併排序算法中最好、最壞、平均的時間性能。
歸併排序的空間複雜度為O(n+logn)
歸併排序是一種比較佔內存，但是效率高且穩定的算法。

6.2歸併排序的實現（迭代非遞歸實現）

用迭代實現的話，可以從最小的序列開始歸併直到完成。

#pragma - 7.歸併排序（迭代實現）
void MergePass(int SR[], int TR[], int s, int n){
 
 int i = 1;
 int j;
 
 while (i <= n-2*s+1) {
 Merge(SR, TR, i, i+s-1, i+2*s-1);
 i = i+2*s;
 }
 
 if (i < n-s+1)
 Merge(SR, TR, i, i+s-1, n);
 else
 for (j = i; j <= n; j++)
 TR[j] = SR[j];
}
void MergeSort2(SqList *L){
 
 int * TR = (int *)malloc(sizeof(L->length*sizeof(int)));
 int k = 1;
 
 while (k < L->length) {
 MergePass(L->r, TR, k, L->length);
 k = 2*k;
 
 MergePass(TR, L->r, k, L->length);
 k = 2*k;
 }
}

歸併的迭代實現總結

非遞歸的迭代方法，避免了遞歸時深度為log2n的棧空間，空間只是用到申請歸併臨時用的TR數組，因此空間複雜度為O(n).
並且相對於遞歸，在時間性能上也有一定的提升，所以使用歸併時，儘量使用非遞歸實現。

七、快速排序

快速排序(Quick Sort)的基本思想是：

通過一趟排序將待排序記錄分割成獨立的兩部分
其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小；
則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。

快速排序的實現思路

選取一個關鍵字，放到一個位置，使得它的左邊的值都比它小，右邊的值都比它大，這個關鍵字叫做樞軸（pivot)
然後分別對左邊和右邊進行排序。

快速排序的代碼實現

#pragma - 8.快速排序
int Partition(SqList * L, int low, int high){
 
 int pivotkey;
 pivotkey = L->r[low];
 
 while (low < high) {
 while (low < high && L->r[high] >= pivotkey)
 high --;
 swap(L, low, high);
 
 while (low < high && L->r[low] <= pivotkey)
 high++;
 swap(L, low, high);
 }
 
 return low;
}
void QSort(SqList *L, int low, int high){
 
 int pivot;
 if (low < high) {
 pivot = Partition(L, low, high);
 QSort(L, low, pivot-1);
 QSort(L, pivot+1, high);
 }
}
void QuickSort(SqList *L){
 QSort(L, 1, L->length);
}

快速排序的代碼說明

Partition函數就是將選取的pivotkey不斷交換，將比它小的換到它的左邊，比它大的交換到它的右邊，它也在交換中不斷更改自己的位置，直到完全滿足這個要求為止。
快速排序的時間性能取決於快速遞歸的深度，快排的時間複雜度為O(nlogn)。
快速排序的空間複雜度主要是遞歸造成的棧空間的使用，平均情況下空間複雜度為O(nlogn)。
由於關鍵字的比較和交換是跳躍進行的，因此，快排是一種不穩定的排序算法

快速排序的優化

優化選取樞軸
在上面的代碼中，選取樞軸的方式為：
pivotkey = L->r[low]，即用序列的第一個元素作為樞軸，這是理想情況下 L->r[low]是中間數。
但是對於其他情況，這種固定選取第一個關鍵子作為首個樞軸的方法就不是很合理。
於是可以用下面的方法優化：

三數取中(median-of-three)法：
取三個關鍵子進行排序，將中間數作為樞軸，一般取左端、右端和中間三個數，也可以隨機選取。
九數取中(median-of-nine)法：
先從數組中分三次取樣，每次取三個數，三個樣品各取中數，然後從這三個數當中再取出一箇中數作為樞軸

三數取中(median-of-three)法代碼：


 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];

優化不必要的交換
優化小數組時的排序方案
優化遞歸操作

快速排序優化後的代碼

int Partition1(SqList * L, int low, int high){
 
 int pivotkey;
 
 int m = low + (high - low)/2;
 
 if (L->r[low] > L->r[high])
 swap(L, low, high);
 
 if (L->r[m] > L->r[high])
 swap(L, high, m);
 if (L->r[m] > L->r[low])
 swap(L, m, low);
 
 pivotkey = L->r[low];
 L->r[0] = pivotkey;
 
 while (low < high) {
 while (low < high && L->r[high] >= pivotkey)
 high--;
 L->r[low] = L->r[high];
 
 while (low < high && L->r[low] <= pivotkey)
 low++;
 L->r[high] = L->r[low];
 }
 
 L->r[low] = L->r[0];
 
 return low;
}
void QSort1(SqList *L, int low, int high){
 
 int pivot;
 if ((high -low) > MAX_LINEGIH_INSERT_SORT) {
 while (low < high) {
 pivot = Partition1(L, low, high);
 QSort1(L, low, pivot-1);
 
 low = pivot+1;
 }
 }else
 InsertSort(L);
}
void QuickSort1(SqList *L){
 QSort1(L, 1, L->length);
}

希爾排序相當於直接插入排序的升級，同屬於插入排序類
堆排序相當於簡單選擇排序的升級，同屬於選擇排序類
快速排序相當於冒泡排序的升級，同屬於交換排序類

算法 － 七大排序算法詳細介紹

相關推薦

算法－七大排序算法詳細介紹