基于分治思想的排序算法：歸并排序、快速排序

一、歸并排序（Merge Sort）

1、基本思想

基于分治（分而治之）思想，歸并排序算法不斷地將原數組分成大小相等的兩個子數組(可能相差1)，最終當劃分的子數組大小為1時；然后對前后兩部分分別排序，再將劃分的有序子數組合并成一個更大的有序數組。

• 分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了。

2、合并相鄰有序子序列（治）

例如：求解數組 a[p…r] 等價于 求解有序的a[p…q]和a[q+1…r]的合并，其中 q= (p+r)/2。

過程：

申請一個臨時數組tmp，其大小與a[p…r]相同；

設置游標 i 和 j，分別指向a[p…q]和a[q+1…r]的第一個元素；2.設置游標 i 和 j，分別指向a[p…q]和a[q+1…r]的第一個元素；

比較 a[i] 和 a[j]，若 a[i]<=a[j]，將a[i]放入臨時數組tmp，并 i 后移一位，否則將 a[j] 放入臨時數組tmp，并 j 后移一位；

直到一個子數組中的所有數據都放入到臨時數組中，再把另一個數組中的數據依次加入到臨時數組的末尾。所獲得的臨時數組就是兩個數組的合并結果

把臨時數組tmp中的數據拷貝到原數組 a[p…r]

3、實現

void merge_sort(int *data, int start, int end, int *result) {if(1 == end - start)//如果區間中只有兩個元素，則對這兩個元素進行排序{if(data[start] > data[end]){int temp = data[start];data[start] = data[end];data[end] = temp;}return;}else if(0 == end - start)//如果只有一個元素，則不用排序return;else{//繼續劃分子區間，分別對左右子區間進行排序 merge_sort(data,start,(end-start+1)/2+start,result);merge_sort(data,(end-start+1)/2+start+1,end,result);//開始歸并已經排好序的start到end之間的數據merge(data,start,end,result);//把排序后的區間數據復制到原始數據中去for(int i = start;i <= end;++i)data[i] = result[i];} }void merge(int *data,int start,int end,int *result) {int left_length = (end - start + 1) / 2 + 1;//左部分區間的數據元素的個數int left_index = start;int right_index = start + left_length;int result_index = start;while(left_index < start + left_length && right_index < end+1){//對分別已經排好序的左區間和右區間進行合并if(data[left_index] <= data[right_index])result[result_index++] = data[left_index++];elseresult[result_index++] = data[right_index++];}while(left_index < start + left_length)result[result_index++] = data[left_index++];while(right_index < end+1)result[result_index++] = data[right_index++]; }

4、分析

（1）穩定排序算法

• 關鍵在于合并相鄰有序子序列的部分。
• 在合并的過程中，若a[p…q]和a[q+1…r]之間有值相同的元素，那么將a[p…q]中的元素放入tmp數組中，就使得值相同的元素，在合并前后的先后順序不變。

（2）時間復雜度

a、遞歸方法的時間復雜度

遞歸方法：一個問題A可以分解為多個子問題B、C，那么求解問題A可分解為求解B、C。問題B、C解決之后，我們將B、C的結果合并成問題A的結果。

定義求解問題A的時間是T(a)，求解問題B、C的時間分別是 T(b) 和 T(c) ，則可得遞歸公式：

T(a) = T(b) + T(c) + K其中，K 等于將兩個子問題 B、C 的結果合并成問題A的結果所消耗的時間

==》遞歸代碼的時間復雜度也可以寫成遞推公式

b、歸并排序的時間復雜度

• 假設對 n 個元素進行歸并排序需要 T(n)，那分解成兩個子數組排序的時間都是 T(n/2);
• 合并相鄰有序子序列的時間復雜度是 O(n) 。

可得 ==》

T(1) = C; //n=1 時，只需要常量級的執行時間，所以表示為 C。 T(n) = 2 * T(n/2) + n; // n > 1

分解可得 ==》

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^k) = T(1) 求得
==》k=log₂n
==》將 k 值帶入，可得 T(n) = Cn + nlog₂n
==》時間復雜度：T(n) = O(nlogn)

（3）空間復雜度——O(n)

每次合并操作都需申請額外的內存空間，但在完成之后，臨時內存空間就被釋放掉。
==》 在任意時刻，CPU只會有一個函數在執行，也就是只有一個臨時內存空間在使用 ==》最大不會超過 n 個數據的大小：O(n)

二、快速排序 (QuickSort)

1、基本思想

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

快速排序的流程：
(1) 從數列中挑出一個基準值。
(2) 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的后面(相同的數可以到任一邊)；在這個分區退出之后，該基準就處于數列的中間位置。
(3) 遞歸地把"基準值前面的子數列"和"基準值后面的子數列"進行排序。

2、偽代碼

partition(A, p, r) {key := A[r];i := p;for j := p to r-1 do {if A[j] < key {swap A[i] with A[j]i := i + 1}}swap A[i] with A[r]return i }

通過游標 i 把 A[p…r-1] 分成兩部分。A[p…i-1] 的元素都是小于 key 的，我們暫且叫它“已處理區間”，A[i…r-1] 是“未處理區間”。我們每次都從未處理的區間 A[i…r-1] 中取一個元素 A[j]，與 key 對比，如果小于 key，則將其加入到已處理區的尾部，也就是 A[i] 的位置。

3、性能分析

• 不穩定
• 原地排序——空間復雜度為O(1)
• 時間復雜度：大部分情況下的時間復雜度都可以做到 O(nlogn)，只有在極端情況下，才會退化到 O(n²)。

總結

以上是生活随笔為你收集整理的七、排序 (2)的全部內容，希望文章能夠幫你解決所遇到的問題。

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