前面課時中，我們學習了分治法的思想，以及二分查找的實現方法。我們講到，二分查找要求原數組必須有序。其實，由無序到有序，這是算法領域最常見的一類問題，即排序問題。本課時，我們就來學習 4 種常見的排序算法，包括冒泡排序、插入排序、歸并排序以及快速排序。此外，我們還會對這 4 種排序算法的優劣勢進行詳細地對比分析。 #### 什么是排序問題 **排序，就是讓一組無序數據變成有序的過程**。 一般默認這里的有序都是從小到大的排列順序。下面我們先來講講，如何判斷不同的排序算法的優劣。 衡量一個排序算法的優劣，我們主要會從以下 3 個角度進行分析： 1．時間復雜度，具體包括，最好時間復雜度、最壞時間復雜度以及平均時間復雜度。 2．空間復雜度，如果空間復雜度為 1，也叫作原地排序。 3．穩定性，排序的穩定性是指相等的數據對象，在排序之后，順序是否能保證不變。 #### 常見的排序算法及其思想 接下來，我們就開始詳細地介紹一些經典的排序算法。 * [ ] **冒泡排序** * [ ] 1、冒泡排序的原理 從第一個數據開始，依次比較相鄰元素的大小。如果前者大于后者，則進行交換操作，把大的元素往后交換。通過多輪迭代，直到沒有交換操作為止。 冒泡排序就像是在一個水池中處理數據一樣，每次會把最大的那個數據傳遞到最后。  * [ ] 2、冒泡排序的性能 冒泡排序最好時間復雜度是 O(n)，也就是當輸入數組剛好是順序的時候，只需要挨個比較一遍就行了，不需要做交換操作，所以時間復雜度為 O(n)。 冒泡排序最壞時間復雜度會比較慘，是 O(n*n)。也就是說當數組剛好是完全逆序的時候，每輪排序都需要挨個比較 n 次，并且重復 n 次，所以時間復雜度為 O(n*n)。 很顯然，當輸入數組雜亂無章時，它的平均時間復雜度也是 O(n*n)。 冒泡排序不需要額外的空間，所以空間復雜度是 O(1)。冒泡排序過程中，當元素相同時不做交換，所以冒泡排序是穩定的排序算法。代碼如下： ``` public static void main(String[] args) { int[] arr = { 1, 0, 3, 4, 5, -6, 7, 8, 9, 10 }; System.out.println("原始數據: " + Arrays.toString(arr)); for (int i = 1; i < arr.length; i++) { for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } System.out.println("冒泡排序: " + Arrays.toString(arr)); } ``` * [ ] 插入排序 * 1、插入排序的原理 選取未排序的元素，插入到已排序區間的合適位置，直到未排序區間為空。插入排序顧名思義，就是從左到右維護一個已經排好序的序列。直到所有的待排數據全都完成插入的動作。  * 2、插入排序的性能 插入排序最好時間復雜度是 O(n)，即當數組剛好是完全順序時，每次只用比較一次就能找到正確的位置。這個過程重復 n 次，就可以清空未排序區間。 插入排序最壞時間復雜度則需要 O(n*n)。即當數組剛好是完全逆序時，每次都要比較 n 次才能找到正確位置。這個過程重復 n 次，就可以清空未排序區間，所以最壞時間復雜度為 O(n*n)。 插入排序的平均時間復雜度是 O(n*n)。這是因為往數組中插入一個元素的平均時間復雜度為 O(n)，而插入排序可以理解為重復 n 次的數組插入操作，所以平均時間復雜度為 O(n*n)。 插入排序不需要開辟額外的空間，所以空間復雜度是 O(1)。 根據上面的例子可以發現，插入排序是穩定的排序算法。代碼如下： ``` public static void main(String[] args) { int[] arr = { 2, 3, 5, 1, 23, 6, 78, 34 }; System.out.println("原始數據: " + Arrays.toString(arr)); for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i - 1; for (; j >= 0; j--) { if (arr[j] > temp) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = temp; } System.out.println("插入排序: " + Arrays.toString(arr)); } ``` **小結：插入排序和冒泡排序算法的異同點** 接下來我們來比較一下上面這兩種排序算法的異同點： 相同點 * 插入排序和冒泡排序的平均時間復雜度都是 O(n*n)，且都是穩定的排序算法，都屬于原地排序。 差異點 * 冒泡排序每輪的交換操作是動態的，所以需要三個賦值操作才能完成； * 而插入排序每輪的交換動作會固定待插入的數據，因此只需要一步賦值操作。 以上兩種排序算法都比較簡單，通過這兩種算法可以幫助我們對排序的思想建立基本的了解，接下來再介紹一些時間復雜度更低的排序算法，它們的時間復雜度都可以達到 O(nlogn)。 * [ ] 歸并排序 * 1、歸并排序的原理 歸并排序的原理其實就是我們上一課時講的分治法。它首先將數組不斷地二分，直到最后每個部分只包含 1 個數據。然后再對每個部分分別進行排序，最后將排序好的相鄰的兩部分合并在一起，這樣整個數組就有序了。  代碼如下： ``` public static void main(String[] args) { int[] arr = { 49, 38, 65, 97, 76, 13, 27, 50 }; int[] tmp = new int[arr.length]; System.out.println("原始數據: " + Arrays.toString(arr)); customMergeSort(arr, tmp, 0, arr.length - 1); System.out.println("歸并排序: " + Arrays.toString(arr)); } public static void customMergeSort(int[] a, int[] tmp, int start, int end) { if (start < end) { int mid = (start + end) / 2; // 對左側子序列進行遞歸排序 customMergeSort(a, tmp, start, mid); // 對右側子序列進行遞歸排序 customMergeSort(a, tmp,mid + 1, end); // 合并 customDoubleMerge(a, tmp, start, mid, end); } } public static void customDoubleMerge(int[] a, int[] tmp, int left, int mid, int right) { int p1 = left, p2 = mid + 1, k = left; while (p1 <= mid && p2 <= right) { if (a[p1] <= a[p2]) tmp[k++] = a[p1++]; else tmp[k++] = a[p2++]; } while (p1 <= mid) tmp[k++] = a[p1++]; while (p2 <= right) tmp[k++] = a[p2++]; // 復制回原素組 for (int i = left; i <= right; i++) a[i] = tmp[i]; ``` * 2、歸并排序的性能 **對于歸并排序，它采用了二分的迭代方式，復雜度是 logn**。 每次的迭代，需要對兩個有序數組進行合并，這樣的動作在 O(n) 的時間復雜度下就可以完成。因此，**歸并排序的復雜度就是二者的乘積 O(nlogn)。**同時，它的執行頻次與輸入序列無關，因此，歸并排序最好、最壞、平均時間復雜度都是 O(nlogn)。 空間復雜度方面，由于每次合并的操作都需要開辟基于數組的臨時內存空間，所以空間復雜度為 O(n)。歸并排序合并的時候，相同元素的前后順序不變，所以歸并是穩定的排序算法。 * [ ] 快速排序 * 1、快速排序法的原理 快速排序法的原理也是分治法。它的每輪迭代，會選取數組中任意一個數據作為分區點，將小于它的元素放在它的左側，大于它的放在它的右側。再利用分治思想，繼續分別對左右兩側進行同樣的操作，直至每個區間縮小為 1，則完成排序。  代碼參考： ``` public static void main(String[] args) { int[] arr = { 6, 1, 2, 7, 9, 11, 4, 5, 10, 8 }; System.out.println("原始數據: " + Arrays.toString(arr)); customQuickSort(arr, 0, arr.length - 1); System.out.println("快速排序: " + Arrays.toString(arr)); } public void customQuickSort(int[] arr, int low, int high) { int i, j, temp, t; if (low >= high) { return; } i = low; j = high; temp = arr[low]; while (i < j) { // 先看右邊，依次往左遞減 while (temp <= arr[j] && i < j) { j--; } // 再看左邊，依次往右遞增 while (temp >= arr[i] && i < j) { i++; } t = arr[j]; arr[j] = arr[i]; arr[i] = t; } arr[low] = arr[i]; arr[i] = temp; // 遞歸調用左半數組 customQuickSort(arr, low, j - 1); // 遞歸調用右半數組 customQuickSort(arr, j + 1, high); ``` } * 2、快速排序法的性能 在快排的最好時間的復雜度下，如果每次選取分區點時，都能選中中位數，把數組等分成兩個，那么此時的時間復雜度和歸并一樣，都是 O(n*logn)。 而在最壞的時間復雜度下，也就是如果每次分區都選中了最小值或最大值，得到不均等的兩組。那么就需要 n 次的分區操作，每次分區平均掃描 n / 2 個元素，此時時間復雜度就退化為 O(n*n) 了。 快速排序法在大部分情況下，統計上是很難選到極端情況的。因此它平均的時間復雜度是 O(n*logn)。 快速排序法的空間方面，使用了交換法，因此空間復雜度為 O(1)。 很顯然，快速排序的分區過程涉及交換操作，所以快排是不穩定的排序算法。 #### 排序算法的性能分析 我們先思考一下排序算法性能的下限，也就是最差的情況。在前面的課程中，我們寫過求數組最大值的代碼，它的時間復雜度是 O(n)。對于 n 個元素的數組，只要重復執行 n 次最大值的查找就能完成排序。因此排序最暴力的方法，時間復雜度是 O(n*n)。這恰如冒泡排序和插入排序。 當我們利用算法思維去解決問題時，就會想到嘗試分治法。此時，利用歸并排序就能讓時間復雜度降低到 O(nlogn)。然而，歸并排序需要額外開辟臨時空間。一方面是為了保證穩定性，另一方面則是在歸并時，由于在數組中插入元素導致了數據挪移的問題。 為了規避因此而帶來的時間損耗，此時我們采用快速排序。通過交換操作，可以解決插入元素導致的數據挪移問題，而且降低了不必要的空間開銷。但是由于其動態二分的交換數據，導致了由此得出的排序結果并不穩定。 #### 總結 本課時我們講了4 種常見的排序算法，包括冒泡排序、插入排序、歸并排序以及快速排序。這些經典算法沒有絕對的好和壞，它們各有利弊。在工作過程中，需要你根據實際問題的情況來選擇最優的排序算法。 如果對數據規模比較小的數據進行排序，可以選擇時間復雜度為 O(n*n) 的排序算法。因為當數據規模小的時候，時間復雜度 O(nlogn) 和 O(n*n) 的區別很小，它們之間僅僅相差幾十毫秒，因此對實際的性能影響并不大。 但對數據規模比較大的數據進行排序，就需要選擇時間復雜度為 O(nlogn) 的排序算法了。 * 歸并排序的空間復雜度為 O(n)，也就意味著當排序 100M 的數據，就需要 200M 的空間，所以對空間資源消耗會很多。 * 快速排序在平均時間復雜度為 O(nlogn)，但是如果分區點選擇不好的話，最壞的時間復雜度也有可能逼近 O(n*n)。而且快速排序不具備穩定性，這也需要看你所面對的問題是否有穩定性的需求。 最后，如果你在工作中，遇到了與排序相關的困難或經驗，歡迎你在留言區和我分享。