青娱乐在线观看,国产99精品,三级久久久久,日大黑逼视频,a一级黄片,97视频人人,日韩在线观a片高清,一本色道久久综合亚洲精品久久

大家好，我是向同學，我們今天來談談歸并排序算法。

歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

一、算法思想

歸并排序的主要思想是分治法。主要過程是：

1. 將n個元素從中間切開，分成兩部分。

2. 將剩下的數(shù)組通過遞歸的方式一直分割，直到數(shù)組的大小為 1，此時只有一個元素，那么該數(shù)組就是有序的了。

3. 從最底層開始逐步合并兩個排好序的數(shù)列。把兩個數(shù)組大小為1的合并成一個大小為2的有序數(shù)列，再把兩個大小為2有序數(shù)列的合并成4的有序數(shù)列?…?直到全部小的數(shù)組合并起來。

二、思考

那么如何將兩個有序數(shù)列合成一個有序的數(shù)列呢？

我們舉個栗子把，一看就懂啦。

三、舉個栗子

例如有數(shù)組?arr [3,7,8,10,2,4,6,9]; 我們可以把這個數(shù)組分成兩個有序的子序列。

分別為 [3, 7, 8, 10] 和 [2, 4, 6, 9]，并將其合并為有序序列[2,3,4,6,7,8,9,10]。

第一步：

把這兩個小的數(shù)組拆分為 left 數(shù)組和 right 數(shù)組。如下圖所示，使用 i 指向 left 的第一個元素，使用 j 指向 right 的第一個元素。

第二步：

建立一個空數(shù)組 arr ,使用 k 指向數(shù)組第一個元素。

第三步：

比較 i 和 j 所指數(shù)字，將小的數(shù)字放在 k 所指位置。同時將小的數(shù)字所指位置和 k 所指位置向右移一位。

2 < 3 , 將 2 填入 arr 數(shù)組，同時右移 j 和 k。

3 < 4 , 將 3 填入 arr 數(shù)組，同時右移 i 和 k。

4 < 7，將 4 填入 arr 數(shù)組，同時右移 j 和 k。

6 < 7，將 6 填入 arr 數(shù)組，同時右移 j 和 k。

7 < 9，將 7 填入 arr 數(shù)組，同時右移 i 和 k。

8 < 9，將 8 填入 arr 數(shù)組，同時右移 i 和 k。

10 > 9，將 9 填入 arr 數(shù)組，同時右移 j 和 k。

可以發(fā)現(xiàn)此時 right 數(shù)組已經(jīng)填完了，所以此時只需要把 left 數(shù)組剩下的數(shù)字填入 arr 即可。

一頓操作猛如虎，這樣就把兩個有序的數(shù)組通過歸并的方式排好順序啦，是不是很贊。

那么問題來了，難道歸并排序只能排這種有序的數(shù)組么？

那出現(xiàn)一個無序的數(shù)組該咋辦呢？例如這個數(shù)組現(xiàn)在變?yōu)?arr [8,7,2,10,3,9,4,6];

四、問題解決

此刻需要運用分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

其實上面第三部分就是治(conquer)的過程，將兩個有序的序列合成為一個有序的序列。

小栗子：圖解無序序列進行希爾排序。

五、算法實現(xiàn)

#include?

void?merge(int?arr[], int?L, int?M, int?R)?{
??int?LEFT_SIZE = M - L;
??int?RIGHT_SIZE = R - M + 1;
??int?left[LEFT_SIZE];
??int?right[RIGHT_SIZE];
??int?i, j, k;
??
??// 填充左邊的數(shù)組
???for?(i=L; i?????left[i-L] = arr[i];
???}
???
??// 填充右邊的數(shù)組
???for?(i=M; i<=R; i++){
?????right[i-M] = arr[i];
???}
???
// for (int i=0; i
// printf("%d\n",left[i]);
// }
// 
// for (int i=0; i
// printf("%d\n",right[i]);
// }

??// 合并數(shù)組
???i = 0; j = 0; k = L;
???while?(i < LEFT_SIZE && j < RIGHT_SIZE){
?????if?(left[i] < right[j]){
???????arr[k] = left[i];
???????i++;
???????k++;
?????}else{
???????arr[k] = right[j];
???????j++;
???????k++;
?????}
???}
???
???while(i < LEFT_SIZE){
?????arr[k] = left[i];
?????i++;
?????k++; 
???}
???while(j < RIGHT_SIZE){
?????arr[k] = right[j];
?????j++;
?????k++; 
???}
???
}

void?mergeSort(int?arr[], int?L, int?R){
??if?(L == R){
????return;
??}else{
????int?M = (L + R) / 2;
????mergeSort(arr,L,M);
????mergeSort(arr, M+1,R);
????merge(arr, L, M+1,R);
??}
}

int?main(){
// int arr[] = {3,7,8,10,2,4,6,9};
??int?arr[] = {8,7,2,10,3,9,4,6};
??int?L = 0;
??int?M = 4;
??int?R = 7;
??mergeSort(arr,L,R);
??
??for?(int?i=0; i<=R; i++){
????printf("%d\n",arr[i]); 
??}
}

輸出：

六、算法分析

時間復雜度：O(nlogn)。

空間復雜度：O(N)，歸并排序需要一個與原數(shù)組相同長度的數(shù)組做輔助來排序。

穩(wěn)定性：穩(wěn)定，因為交換元素時，可以在相等的情況下做出不移動的限制，所以歸并排序是可以穩(wěn)定的。

七、適用場景

歸并排序需要一個跟待排序數(shù)組同等空間的臨時數(shù)組，因此，使用歸并排序時需要考慮是否有空間上的限制。如果沒有空間上的限制，歸并排序是一個不錯的選擇。

關(guān)注下方公眾號，分享硬核知識

BAT 經(jīng)典算法筆試題-歸并排序算法

一、算法思想

二、思考

三、舉個栗子

四、問題解決

五、算法實現(xiàn)