一看就懂 ! 圖解歸并排序

大家好，我是bigsai，我們今天來(lái)談?wù)剼w并排序算法。
歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

一、算法思想

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

1. 將n個(gè)元素從中間切開(kāi)，分成兩部分。

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

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

二、思考

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

我們舉個(gè)栗子把，一看就懂啦。

三、舉個(gè)栗子

四、問(wèn)題解決

五、算法實(shí)現(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]);
??}
}

六、算法分析

七、適用場(chǎng)景