冒泡、插入、選擇 O(n^2) 基于比較
快排、歸并 O(nlogn) 基于比較
計數、基數、桶 O(n) 不基于比較

一、分治思想

1.分治思想：分治，顧明思意，就是分而治之，將一個大問題分解成小的子問題來解決，小的子問題解決了，大問題也就解決了。

2.分治與遞歸的區別：分治算法一般都用遞歸來實現的。分治是一種解決問題的處理思想，遞歸是一種編程技巧。

二、歸并排序

1.算法原理

先把數組從中間分成前后兩部分，然后對前后兩部分分別進行排序，再將排序好的兩部分合并到一起，這樣整個數組就有序了。這就是歸并排序的核心思想。如何用遞歸實現歸并排序呢？寫遞歸代碼的技巧就是分寫得出遞推公式，然后找到終止條件，最后將遞推公式翻譯成遞歸代碼。遞推公式怎么寫？如下
遞推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
終止條件：p >= r 不用再繼續分解

2.代碼實現

public class MergeSort {// 歸并排序算法, a是數組，n表示數組大小public static void mergeSort(int[] a, int n) {mergeSortInternally(a, 0, n-1);}// 遞歸調用函數private static void mergeSortInternally(int[] a, int p, int r) {// 遞歸終止條件if (p >= r) return;// 取p到r之間的中間位置q,防止（p+r）的和超過int類型最大值int q = p + (r - p)/2;// 分治遞歸mergeSortInternally(a, p, q);mergeSortInternally(a, q+1, r);// 將A[p...q]和A[q+1...r]合并為A[p...r]merge(a, p, q, r);}private static void merge(int[] a, int p, int q, int r) {int i = p;int j = q+1;int k = 0; // 初始化變量i, j, kint[] tmp = new int[r-p+1]; // 申請一個大小跟a[p...r]一樣的臨時數組while (i<=q && j<=r) {if (a[i] <= a[j]) {tmp[k++] = a[i++]; // i++等于i:=i+1} else {tmp[k++] = a[j++];}}// 判斷哪個子數組中有剩余的數據int start = i;int end = q;if (j <= r) {start = j;end = r;}// 將剩余的數據拷貝到臨時數組tmpwhile (start <= end) {tmp[k++] = a[start++];}// 將tmp中的數組拷貝回a[p...r]for (i = 0; i <= r-p; ++i) {a[p+i] = tmp[i];}}/*** 合并(哨兵)** @param arr* @param p* @param q* @param r*/private static void mergeBySentry(int[] arr, int p, int q, int r) {int[] leftArr = new int[q - p + 2];int[] rightArr = new int[r - q + 1];for (int i = 0; i <= q - p; i++) {leftArr[i] = arr[p + i];}// 第一個數組添加哨兵（最大值）leftArr[q - p + 1] = Integer.MAX_VALUE;for (int i = 0; i < r - q; i++) {rightArr[i] = arr[q + 1 + i];}// 第二個數組添加哨兵（最大值）rightArr[r-q] = Integer.MAX_VALUE;int i = 0;int j = 0;int k = p;while (k <= r) {// 當左邊數組到達哨兵值時，i不再增加，直到右邊數組讀取完剩余值，同理右邊數組也一樣if (leftArr[i] <= rightArr[j]) {arr[k++] = leftArr[i++];} else {arr[k++] = rightArr[j++];}}} }

3.性能分析

1）算法穩定性：

歸并排序穩不穩定關鍵要看merge()函數，也就是兩個子數組合并成一個有序數組的那部分代碼。在合并的過程中，如果 A[p…q] 和 A[q+1…r] 之間有值相同的元素，那我們就可以像偽代碼中那樣，先把 A[p…q] 中的元素放入tmp數組，這樣 就保證了值相同的元素，在合并前后的先后順序不變。所以，歸并排序是一種穩定排序算法。

2）時間復雜度：分析歸并排序的時間復雜度就是分析遞歸代碼的時間復雜度

如何分析遞歸代碼的時間復雜度？
遞歸的適用場景是一個問題a可以分解為多個子問題b、c，那求解問題a就可以分解為求解問題b、c。問題b、c解決之后，我們再把b、c的結果合并成a的結果。若定義求解問題a的時間是T(a)，則求解問題b、c的時間分別是T(b)和T?，那就可以得到這樣的遞推公式：T(a) = T(b) + T? + K，其中K等于將兩個子問題b、c的結果合并成問題a的結果所消耗的時間。這里有一個重要的結論：不僅遞歸求解的問題可以寫成遞推公式，遞歸代碼的時間復雜度也可以寫成遞推公式。套用這個公式，那么歸并排序的時間復雜度就可以表示為：

T(1) = C； n=1 時，只需要常量級的執行時間，所以表示為 C。 T(n) = 2*T(n/2) + n； n>1，其中n就是merge()函數合并兩個子數組的的時間復雜度O(n)。T(n) = 2*T(n/2) + n= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n......= 2^k * T(n/2^k) + k * n...... ......

T(n) = 2^kT(n/2^k)+kn。當 T(n/2^k)=T(1) 時，也就是 n/2^k=1，我們得到 k=log₂n 。我們將 k 值代入上面的公式，得到 T(n)=Cn+nlog₂n 。如果我們用大 O 標記法來表示的話，T(n) 就等于 O(nlogn)。所以歸并排序的時間復雜度是 O(nlogn)。
3）空間復雜度：歸并排序算法不是原地排序算法，空間復雜度是O(n)
為什么？因為歸并排序的合并函數，在合并兩個數組為一個有序數組時，需要借助額外的存儲空間。為什么空間復雜度是O(n)而不是O(nlogn)呢？如果我們按照分析遞歸的時間復雜度的方法，通過遞推公式來求解，那整個歸并過程需要的空間復雜度就是O(nlogn)，但這種分析思路是有問題的！因為，在實際上，遞歸代碼的空間復雜度并不是像時間復雜度那樣累加，而是這樣的過程，即在每次合并過程中都需要申請額外的內存空間，但是合并完成后，臨時開辟的內存空間就被釋放掉了，在任意時刻，CPU只會有一個函數在執行，也就只會有一個臨時的內存空間在使用。臨時空間再大也不會超過n個數據的大小，所以空間復雜度是O(n)。

三、快速排序

1.算法原理

快排的思想是這樣的：如果要排序數組中下標從p到r之間的一組數據，我們選擇p到r之間的任意一個數據作為pivot（分區點）。然后遍歷p到r之間的數據，將小于pivot的放到左邊，將大于pivot的放到右邊，將povit放到中間。經過這一步之后，數組p到r之間的數據就分成了3部分，前面p到q-1之間都是小于povit的，中間是povit，后面的q+1到r之間是大于povit的。根據分治、遞歸的處理思想，我們可以用遞歸排序下標從p到q-1之間的數據和下標從q+1到r之間的數據，直到區間縮小為1，就說明所有的數據都有序了。
遞推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
終止條件：p >= r

2.代碼實現

/*** 快速排序** @param arr*/public static void quickSort(int[] arr, int left, int right) {if (left >= right) {return;}int q = partition2(arr, left, right);quickSort(arr, left, q - 1);quickSort(arr, q + 1, right);}private static int partition(int[] arr, int left, int right) {int pivot = arr[right];int i = left;for (int j = left; j < right; j++) {if (arr[j] < pivot) {if (i == j) {++i;} else {int tmp = arr[i];arr[i++] = arr[j];arr[j] = tmp;}}}int tmp = arr[i];arr[i] = arr[right];arr[right] = tmp;return i;}private static int partition2(int[] arr, int left, int right) {// 三數取中法 , 隨機數在這里寫int middle = (left + right) / 2;int pivot = arr[middle];// 交換到最右邊int val = arr[right];arr[right] = pivot;arr[middle] = val;int i = left;for (int j = left; j < right; j++) {if (arr[j] < pivot) {if (i == j) {++i;} else {int tmp = arr[i];arr[i++] = arr[j];arr[j] = tmp;}}}int tmp = arr[i];arr[i] = arr[right];arr[right] = tmp;return i;}/*** 三向切分快速排序** @param arr* @param left* @param right* @return*/private static void quickSort3(int[] arr, int left, int right) {if (left >= right) {return;}int l = left;int k = left + 1;int r = right;int pivot = arr[l];while (k <= r) {if (arr[k] < pivot) {int tmp = arr[l];arr[l] = arr[k];arr[k] = tmp;l++;k++;} else if (arr[k] == pivot) {k++;} else {if (arr[r] > pivot) {r--;} else if (arr[r] == pivot) {int tmp = arr[k];arr[k] = arr[r];arr[r] = tmp;k++;r--;} else {int tmp = arr[l];arr[l] = arr[r];arr[r] = arr[k];arr[k] = tmp;l++;k++;r--;}}}quickSort(arr, left, l - 1);quickSort(arr, r + 1, right);}/*** 雙軸快速排序** @param arr* @param left* @param right*/private static void quickSort4(int[] arr, int left, int right) {if (left >= right) {return;}int l = left;int k = left + 1;int r = right;// 判斷pivot1 與 pivot2 大小if (arr[l] > arr[r]) {int tmp = arr[l];arr[l] = arr[r];arr[r] = tmp;}int pivot1 = arr[l];int pivot2 = arr[r];while (k < r) {if (arr[k] < pivot1) {l++;if (l != k) {int tmp = arr[l];arr[l] = arr[k];arr[k] = tmp;}k++;} else if (arr[k] >= pivot1 && arr[k] <= pivot2) {k++;} else {--r;if (arr[r] > pivot2) {} else if (arr[r] >= pivot1 && arr[r] <= pivot2) {int tmp = arr[k];arr[k] = arr[r];arr[r] = tmp;k++;} else {l++;int tmp = arr[l];arr[l] = arr[r];arr[r] = arr[k];arr[k] = tmp;k++;}}}// 交換pivot1 和 pivot2arr[left] = arr[l];arr[l] = pivot1;arr[right] = arr[r];arr[r] = pivot2;quickSort(arr, left, l - 1);quickSort(arr, l + 1, r - 1);quickSort(arr, r + 1, right);}

3.性能分析

1）算法穩定性：

因為分區過程中涉及交換操作，如果數組中有兩個8，其中一個是pivot，經過分區處理后，后面的8就有可能放到了另一個8的前面，先后順序就顛倒了，所以快速排序是不穩定的排序算法。比如數組[1,2,3,9,8,11,8]，取后面的8作為pivot，那么分區后就會將后面的8與9進行交換。

2）時間復雜度：最好、最壞、平均情況

快排也是用遞歸實現的，所以時間復雜度也可以用遞推公式表示。
如果每次分區操作都能正好把數組分成大小接近相等的兩個小區間，那快排的時間復雜度遞推求解公式跟歸并的相同。
T(1) = C； n=1 時，只需要常量級的執行時間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1
所以，快排的時間復雜度也是O(nlogn)。
如果數組中的元素原來已經有序了，比如1，3，5，6，8，若每次選擇最后一個元素作為pivot，那每次分區得到的兩個區間都是不均等的，需要進行大約n次的分區，才能完成整個快排過程，而每次分區我們平均要掃描大約n/2個元素，這種情況下，快排的時間復雜度就是O(n^2)。
前面兩種情況，一個是分區及其均衡，一個是分區極不均衡，它們分別對應了快排的最好情況時間復雜度和最壞情況時間復雜度。那快排的平均時間復雜度是多少呢？T(n)大部分情況下是O(nlogn)，只有在極端情況下才是退化到O(n^2)，而且我們也有很多方法將這個概率降低。

3）空間復雜度：快排是一種原地排序算法，空間復雜度是O(1)

四、歸并排序與快速排序的區別

歸并和快排用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區別在哪里呢？

1.歸并排序，是先遞歸調用，再進行合并，合并的時候進行數據的交換。所以它是自下而上的排序方式。何為自下而上？就是先解決子問題，再解決父問題。

2.快速排序，是先分區，在遞歸調用，分區的時候進行數據的交換。所以它是自上而下的排序方式。何為自上而下？就是先解決父問題，再解決子問題。

筆記整理來源： 王爭 數據結構與算法之美

總結

以上是生活随笔為你收集整理的【数据结构与算法】快排、归并 O(nlogn) 基于比较的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。