大家對(duì)于排序應(yīng)該是挺熟悉的吧，馬士兵老師特意為排序出了一波視頻，當(dāng)然文章是轉(zhuǎn)自博客園的，馬士兵老師的視頻觀(guān)看請(qǐng)點(diǎn)擊下方的了解更多

概要

本章介紹排序算法中的歸并排序。內(nèi)容包括：

1. 歸并排序介紹

2. 歸并排序圖文說(shuō)明

3. 歸并排序的時(shí)間復(fù)雜度和穩(wěn)定性

4. 歸并排序?qū)崿F(xiàn)

4.1 歸并排序C實(shí)現(xiàn)

4.2 歸并排序C++實(shí)現(xiàn)

4.3 歸并排序Java實(shí)現(xiàn)

---

更多排序和算法請(qǐng)參考：數(shù)據(jù)結(jié)構(gòu)與算法系列 目錄

歸并排序介紹

將兩個(gè)的有序數(shù)列合并成一個(gè)有序數(shù)列，我們稱(chēng)之為"歸并"。

歸并排序(Merge Sort)就是利用歸并思想對(duì)數(shù)列進(jìn)行排序。根據(jù)具體的實(shí)現(xiàn)，歸并排序包括"從上往下"和"從下往上"2種方式。

1. 從下往上的歸并排序：將待排序的數(shù)列分成若干個(gè)長(zhǎng)度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為4的有序數(shù)列，再將它們兩兩合并；直接合并成一個(gè)數(shù)列為止。這樣就得到了我們想要的排序結(jié)果。(參考下面的圖片)

2. 從上往下的歸并排序：它與"從下往上"在排序上是反方向的。它基本包括3步：

① 分解 -- 將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn) mid = (low + high)/2;

② 求解 -- 遞歸地對(duì)兩個(gè)子區(qū)間a[low...mid] 和 a[mid+1...high]進(jìn)行歸并排序。遞歸的終結(jié)條件是子區(qū)間長(zhǎng)度為1。

③ 合并 -- 將已排序的兩個(gè)子區(qū)間a[low...mid]和 a[mid+1...high]歸并為一個(gè)有序的區(qū)間a[low...high]。

下面的圖片很清晰的反映了"從下往上"和"從上往下"的歸并排序的區(qū)別。

歸并排序圖文說(shuō)明

歸并排序(從上往下)代碼

/* * 將一個(gè)數(shù)組中的兩個(gè)相鄰有序區(qū)間合并成一個(gè) * * 參數(shù)說(shuō)明： * a -- 包含兩個(gè)有序區(qū)間的數(shù)組 * start -- 第1個(gè)有序區(qū)間的起始地址。 * mid -- 第1個(gè)有序區(qū)間的結(jié)束地址。也是第2個(gè)有序區(qū)間的起始地址。 * end -- 第2個(gè)有序區(qū)間的結(jié)束地址。 */void merge(int a[], int start, int mid, int end){ int *tmp = (int *)malloc((end-start+1)*sizeof(int)); // tmp是匯總2個(gè)有序區(qū)的臨時(shí)區(qū)域 int i = start; // 第1個(gè)有序區(qū)的索引 int j = mid + 1; // 第2個(gè)有序區(qū)的索引 int k = 0; // 臨時(shí)區(qū)域的索引 while(i <= mid && j <= end) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while(i <= mid) tmp[k++] = a[i++]; while(j <= end) tmp[k++] = a[j++]; // 將排序后的元素，全部都整合到數(shù)組a中。 for (i = 0; i < k; i++) a[start + i] = tmp[i]; free(tmp);}/* * 歸并排序(從上往下) * * 參數(shù)說(shuō)明： * a -- 待排序的數(shù)組 * start -- 數(shù)組的起始地址 * endi -- 數(shù)組的結(jié)束地址 */void merge_sort_up2down(int a[], int start, int end){ if(a==NULL || start >= end) return ; int mid = (end + start)/2; merge_sort_up2down(a, start, mid); // 遞歸排序a[start...mid] merge_sort_up2down(a, mid+1, end); // 遞歸排序a[mid+1...end] // a[start...mid] 和 a[mid...end]是兩個(gè)有序空間， // 將它們排序成一個(gè)有序空間a[start...end] merge(a, start, mid, end);}

從上往下的歸并排序采用了遞歸的方式實(shí)現(xiàn)。它的原理非常簡(jiǎn)單，如下圖：

通過(guò)"從上往下的歸并排序"來(lái)對(duì)數(shù)組{80,30,60,40,20,10,50,70}進(jìn)行排序時(shí)：

1. 將數(shù)組{80,30,60,40,20,10,50,70}看作由兩個(gè)有序的子數(shù)組{80,30,60,40}和{20,10,50,70}組成。對(duì)兩個(gè)有序子樹(shù)組進(jìn)行排序即可。

2. 將子數(shù)組{80,30,60,40}看作由兩個(gè)有序的子數(shù)組{80,30}和{60,40}組成。

將子數(shù)組{20,10,50,70}看作由兩個(gè)有序的子數(shù)組{20,10}和{50,70}組成。

3. 將子數(shù)組{80,30}看作由兩個(gè)有序的子數(shù)組{80}和{30}組成。

將子數(shù)組{60,40}看作由兩個(gè)有序的子數(shù)組{60}和{40}組成。

將子數(shù)組{20,10}看作由兩個(gè)有序的子數(shù)組{20}和{10}組成。

將子數(shù)組{50,70}看作由兩個(gè)有序的子數(shù)組{50}和{70}組成。

歸并排序(從下往上)代碼

/* * 對(duì)數(shù)組a做若干次合并：數(shù)組a的總長(zhǎng)度為len，將它分為若干個(gè)長(zhǎng)度為gap的子數(shù)組； * 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。 * * 參數(shù)說(shuō)明： * a -- 待排序的數(shù)組 * len -- 數(shù)組的長(zhǎng)度 * gap -- 子數(shù)組的長(zhǎng)度 */void merge_groups(int a[], int len, int gap){ int i; int twolen = 2 * gap; // 兩個(gè)相鄰的子數(shù)組的長(zhǎng)度 // 將"每2個(gè)相鄰的子數(shù)組" 進(jìn)行合并排序。 for(i = 0; i+2*gap-1 < len; i+=(2*gap)) { merge(a, i, i+gap-1, i+2*gap-1); } // 若 i+gap-1 < len-1，則剩余一個(gè)子數(shù)組沒(méi)有配對(duì)。 // 將該子數(shù)組合并到已排序的數(shù)組中。 if ( i+gap-1 < len-1) { merge(a, i, i + gap - 1, len - 1); }}/* * 歸并排序(從下往上) * * 參數(shù)說(shuō)明： * a -- 待排序的數(shù)組 * len -- 數(shù)組的長(zhǎng)度 */void merge_sort_down2up(int a[], int len){ int n; if (a==NULL || len<=0) return ; for(n = 1; n < len; n*=2) merge_groups(a, len, n);}

從下往上的歸并排序的思想正好與"從下往上的歸并排序"相反。如下圖：

通過(guò)"從下往上的歸并排序"來(lái)對(duì)數(shù)組{80,30,60,40,20,10,50,70}進(jìn)行排序時(shí)：

1. 將數(shù)組{80,30,60,40,20,10,50,70}看作由8個(gè)有序的子數(shù)組{80},{30},{60},{40},{20},{10},{50}和{70}組成。

2. 將這8個(gè)有序的子數(shù)列兩兩合并。得到4個(gè)有序的子樹(shù)列{30,80},{40,60},{10,20}和{50,70}。

3. 將這4個(gè)有序的子數(shù)列兩兩合并。得到2個(gè)有序的子樹(shù)列{30,40,60,80}和{10,20,50,70}。

4. 將這2個(gè)有序的子數(shù)列兩兩合并。得到1個(gè)有序的子樹(shù)列{10,20,30,40,50,60,70,80}。

歸并排序的時(shí)間復(fù)雜度和穩(wěn)定性

歸并排序時(shí)間復(fù)雜度

歸并排序的時(shí)間復(fù)雜度是O(N*lgN)。

假設(shè)被排序的數(shù)列中有N個(gè)數(shù)。遍歷一趟的時(shí)間復(fù)雜度是O(N)，需要遍歷多少次呢？

歸并排序的形式就是一棵二叉樹(shù)，它需要遍歷的次數(shù)就是二叉樹(shù)的深度，而根據(jù)完全二叉樹(shù)的可以得出它的時(shí)間復(fù)雜度是O(N*lgN)。

歸并排序穩(wěn)定性

歸并排序是穩(wěn)定的算法，它滿(mǎn)足穩(wěn)定算法的定義。

算法穩(wěn)定性 -- 假設(shè)在數(shù)列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。則這個(gè)排序算法是穩(wěn)定的！

歸并排序?qū)崿F(xiàn)

下面給出歸并排序的三種實(shí)現(xiàn)：C、C++和Java。這三種實(shí)現(xiàn)的原理和輸出結(jié)果都是一樣的，每一種實(shí)現(xiàn)中都包括了"從上往下的歸并排序"和"從下往上的歸并排序"這2種形式。

歸并排序C實(shí)現(xiàn)

實(shí)現(xiàn)代碼(merge_sort.c)

View Code

歸并排序C++實(shí)現(xiàn)

實(shí)現(xiàn)代碼(MergeSort.cpp)

View Code

歸并排序Java實(shí)現(xiàn)

實(shí)現(xiàn)代碼(MergeSort.java)

View Code

上面3種實(shí)現(xiàn)的原理和輸出結(jié)果都是一樣的。下面是它們的輸出結(jié)果：

before sort:80 30 60 40 20 10 50 70 after sort:10 20 30 40 50 60 70 80

文章原作者：http://www.cnblogs.com/skywang12345/p/3602369.html

總結(jié)

以上是生活随笔為你收集整理的归并排序 java_马士兵说之归并排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。