各種排序算法總結

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列。

1、選擇排序

　　選擇排序是一種直觀簡單的排序算法，它每次從待排序的數據元素中選出最小(或者最大)元素存放到序列的起始位置，直到全部待排序的數據元素排完。注意，選擇排序並不是穩定的排序。

 1 /*
 2  * @brief select sort
 3  * @param [in] arr: the array be sorted
 4  *           [in] length: the array size
 5  * @return void
 6  */
 7 void SelectSort(int arr[], int length)
 8 {
 9     for (int i = 0; i < length; i++) {
10         int min = i;
11         for (int j = i + 1; j < length; j++) {
12             if (arr[min] < arr[j]) {
13                 min = j;
14             }
15         }
16         if (min != i) {
17             swap(arr[min], arr[i]);
18         }
19     }
20 }

2、冒泡排序

　　冒泡排序也是一種直觀簡單的排序算法，它重復地走訪要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。冒泡排序是一種穩定的排序。

 1 /*
 2  * @brief bubble sort
 3  * @param [in] arr: the array be sorted
 4  *          [in] length: the array size
 5  * @return void
 6  */
 7 void BubbleSort(int arr[], int length)
 8 {
 9     for (int i = 0; i < length; i++) {
10         for (int j = 0; j < length - i - 1; j++) {
11             if (arr[j] > arr[j + 1]) {
12                 swap(arr[j], arr[j + 1]);
13             }
14         }
15     }
16 }

3、插入排序

　　插入排序基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的元素序列中適當位置上，直到全部插入完為止。插入排序是穩定的排序算法。

 1 /*
 2  * @brief insert sort
 3  * @param [in] arr: the array be sorted
 4  *          [in] length: the array size
 5  * @return void
 6  */
 7 void InsertSort(int arr[], int length)
 8 {
 9     for (int i = 0; i < length; i++) {
10         for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
11             swap(arr[j], arr[j - 1]);
12         }
13     }
14 }
15 /* 這是插入排序的第二種寫法 */
16 void InsertSort2(int arr[], int length)
17 {
18     for (int i = 0; i < length; i++)
19     {
20         int x = arr[i], j;
21         for (j = i; j > 0 && arr[j - 1] > x; j--)
22             arr[j] = arr[j - 1];
23         arr[j] = x;
24     }
25 }

4、希爾排序

　　希爾排序(Shell Sort)是插入排序的一種，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個數組恰被分成一組，算法便終止。

 1 /*
 2 * @brief shell sort
 3 * @param [in] arr: the array be sorted
 4 *          [in] length: the array size
 5 * @return void
 6 */
 7 void ShellSort(int arr[], int length)
 8 {
 9     for (int inc = length / 2; inc > 0; inc /= 2) {
10         for (int i = inc; i < length; i++) {
11             for (int j = i; j >= inc && arr[j - inc] > arr[j]; j -= inc) {
12                 swap(arr[j], arr[j - inc]);
13             }
14         }
15     }
16 }

5、快速排序

　　快速排序的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

 1 /*
 2  * 快速排序
 3  * 快速排序是一種分治的排序算法，它將一個數組分成兩個子數組，將兩部分獨立地排序。
 4  * 快速排序和歸並排序是互補的：歸並排序將數組分成兩個子數組分別排序，並將有序的子數組歸並以將整個數組排序；
 5  * 而快速排序的方式是當兩個子數組有序時整個數組也就自然有序了。歸並排序中，遞歸發生在處理整個數組之前，
 6  * 一個數組被分為兩半；快速排序中，遞歸調用發生在處理整個數組之後，切分的位置取決於數組的內容。
 7  */
 8 int Partion(int arr[], int left, int right)
 9 {
10     int x = arr[right];
11     int i, j;
12 
13     for (i = j = left; i < right; i++) {
14         if (arr[i] <= x) {
15             swap(arr[i], arr[j++]);
16         }
17     }
18     swap(arr[j], arr[right]);
19 
20     return j;
21 }
22 void QuickSort(int arr[], int left, int right)
23 {
24     if (left < right) {
25         int mid = Partion(arr, left, right);
26         QuickSort(arr, left, mid - 1);
27         QuickSort(arr, mid + 1, right);
28     }
29 }
30 void QuickSort(int arr[], int length)
31 {
32     QuickSort(arr, 0, length - 1);
33 }

6、歸並排序

　　歸並排序是將兩個有序的數組歸並成一個更大的有序數組。要將一個數組排序，可以先（遞歸的）將他分成兩半分別排序，讓後將結果歸並起來。它能夠保證將任意長度為N的數組排序所需時間和NlogN成正比；它的主要缺點就是所需的額外空間和N成正比。歸並排序是穩定的排序算法。

 1 /*
 2  * 歸並排序
 3  * 歸並排序將數組分成兩個子數組分別排序，並將有序的子數組歸並以將整個數組排序
 4  */
 5 void Merge(int arr[], int aux[], int left, int mid, int right) 
 6 {
 7     int i = left;
 8     int j = mid + 1;
 9     int k = left;
10 
11     while (i <= mid && j <= right) {
12         if (arr[i] > arr[j]) {
13             aux[k++] = arr[j++];
14         }
15         else {
16             aux[k++] = arr[i++];
17         }
18     }
19     while (i <= mid) {
20         aux[k++] = arr[i++];
21     }
22     while (j <= right) {
23         aux[k++] = arr[j++];
24     }
25     for (int i = left; i <= right; i++) {
26         arr[i] = aux[i];
27     }
28 }
29 void MergeSort(int arr[], int aux[], int left, int right)
30 {
31     if (left < right) {
32         int mid = left + (right - left) / 2;
33         MergeSort(arr, aux, left, mid);
34         MergeSort(arr, aux, mid + 1, right);
35         Merge(arr, aux, left, mid, right);
36     }
37 }
38 void MergeSort(int arr[], int length)
39 {
40     int *aux = new int[length];
41     MergeSort(arr, aux, 0, length - 1);
42     delete []aux;
43 }

7、 堆排序

　　堆排序可以分為兩個階段。在堆的構造階段，我們將元使數組重新組織安排進一個堆中；然後在下沉階段，我們從堆中按遞減順序取出所有元素並得到排序結果。堆排序主要工作都是在堆的下沉階段完成的，這裡我們將堆中最大的元素刪除，然後放入堆縮小後數組中空出的位置。

 1 /*
 2  * 堆排序
 3  * 堆排序是用堆來實現的一種排序算法，堆排序分為兩個階段，在堆的構造階段中，我們將原始數據重新組織安排
 4  * 進一個堆中；然後在下沉排序階段，我們從堆中按照遞減順序取出所有元素並得到排序算法
 5  */
 6 void Sink(int arr[], int i, int length)
 7 {
 8     while (2 * i <= length) {
 9         int child = 2 * i;
10         if (child < length && arr[child] < arr[child + 1]) {
11             child++;
12         }
13         if (arr[i] >= arr[child]) {
14             break;
15         }
16 
17         swap(arr[i], arr[child]);
18         i = child;
19     }
20 }
21 void HeapSort(int arr[], int length)
22 {
23     length--; /* 此時length代表數組最後一個元素下標 */
24     for (int i = length / 2; i >= 0; i--) { /* 這裡一定要 i>=0，否則建堆不完全 */
25         Sink(arr, i, length);
26     }
27     
28     while(length >= 0) {
29         swap(arr[0], arr[length--]);
30         Sink(arr, 0, length);
31     }
32 }

8、各種排序算法的穩定性和時間復雜度分析

什麼是排序的穩定性呢？如果一個排序算法能夠保留數組中重復元素的相對位置則可以稱為是穩定的。以下是各個排序算法穩定性總結：

• 選擇排序、快���排序、希爾排序、堆排序不是穩定的排序算法，
• 冒泡排序、插入排序、歸並排序和基數排序是穩定的排序算法。

各個排序時間復雜度總結：

• 冒泡法：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(n^2)。
• 直接插入排序：O(n^2)
• 選擇排序：O(n^2)
• 快速排序：平均時間復雜度log2(n)*n，所有內部排序方法中最高好的，大多數情況下總是最好的。
• 歸並排序：log2(n)*n
• 堆排序：log2(n)*n
• 希爾排序：算法的復雜度為log2(n)*n

下面是一個總的表格，大致總結了我們常見的所有的排序算法的特點。

排序法 平均時間 最差情形 穩定度 額外空間 備注 冒泡 O(n²) O(n²) 穩定 O(1) n小時較好 交換 O(n²) O(n²) 不穩定 O(1) n小時較好 選擇 O(n²) O(n²) 不穩定 O(1) n小時較好 插入 O(n²) O(n²) 穩定 O(1) 大部分已排序時較好 基數 O(log_RB) O(log_RB) 穩定 O(n)

B是真數(0-9)，

R是基數(個十百)

Shell O(nlogn) O(n^s) 1<s<2 不穩定 O(1) s是所選分組 快速 O(nlogn) O(n²) 不穩定 O(nlogn) n大時較好 歸並 O(nlogn) O(nlogn) 穩定 O(1) n大時較好 堆 O(nlogn) O(nlogn) 不穩定 O(1) n大時較好 更多排序算法時間復雜度和穩定性見：http://www.linuxidc.com/Linux/2016-04/129795.htm