合並排序演算法思想

『壹』 歸並排序

先考慮一個簡單的問題：如何在線性的時間內將兩個有序隊列合並為一個有序隊列（並輸出）？

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9

看上面的例子，AB兩個序列都是已經有序的了。在給出數據已經有序的情況下，我們會發現很多神奇的事，比如，我們將要輸出的第一個數一定來自於這兩個序列各自最前面的那個數。兩個數都是1，那麼我們隨便取出一個（比如A隊列的那個1）並輸出：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1

注意，我們取出了一個數，在原數列中刪除這個數。刪除操作是通過移動隊首指針實現的，否則復雜度就高了。
現在，A隊列打頭的數變成3了，B隊列的隊首仍然是1。此時，我們再比較3和1哪個大並輸出小的那個數：

A隊列：1 3 5 7 9
B隊列：1 2 7 8 9
輸出：1 1

接下來的幾步如下：

A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9 A隊列：1 3 5 7 9
B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ==> B隊列：1 2 7 8 9 ……
輸出：1 1 2 輸出：1 1 2 3 輸出：1 1 2 3 5 輸出：1 1 2 3 5 7

我希望你明白了這是怎麼做的。這個做法顯然是正確的，復雜度顯然是線性。

歸並排序(Merge Sort)將會用到上面所說的合並操作。給出一個數列，歸並排序利用合並操作在O(nlogn)的時間內將數列從小到大排序。歸並排序用的是分治(Divide and Conquer)的思想。首先我們把給出的數列平分為左右兩段，然後對兩段數列分別進行排序，最後用剛才的合並演算法把這兩段（已經排過序的）數列合並為一個數列。有人會問「對左右兩段數列分別排序時用的什麼排序」么？答案是：用歸並排序。也就是說，我們遞歸地把每一段數列又分成兩段進行上述操作。你不需要關心實際上是怎麼操作的，我們的程序代碼將遞歸調用該過程直到數列不能再分（只有一個數）為止。
初看這個演算法時有人會誤以為時間復雜度相當高。我們下面給出的一個圖將用非遞歸的眼光來看歸並排序的實際操作過程，供大家參考。我們可以藉助這個圖證明，歸並排序演算法的時間復雜度為O(nlogn)。

[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]

上圖中的每一個「 \ / 」表示的是上文所述的線性時間合並操作。上圖用了4行來圖解歸並排序。如果有n個數，表示成上圖顯然需要O(logn)行。每一行的合並操作復雜度總和都是O(n)，那麼logn行的總復雜度為O(nlogn)。這相當於用遞歸樹的方法對歸並排序的復雜度進行了分析。假設，歸並排序的復雜度為T(n)，T(n)由兩個T(n/2)和一個關於n的線性時間組成，那麼T(n)=2*T(n/2)+O(n)。不斷展開這個式子我們可以同樣可以得到T(n)=O(nlogn)的結論，你可以自己試試。如果你能在線性的時間里把分別計算出的兩組不同數據的結果合並在一起，根據T(n)=2*T(n/2)+O(n)=O(nlogn)，那麼我們就可以構造O(nlogn)的分治演算法。這個結論後面經常用。我們將在計算幾何部分舉一大堆類似的例子。
如果你第一次見到這么詭異的演算法，你可能會對這個感興趣。分治是遞歸的一種應用。這是我們第一次接觸遞歸運算。下面說的快速排序也是用的遞歸的思想。遞歸程序的復雜度分析通常和上面一樣，主定理(Master Theory)可以簡化這個分析過程。主定理和本文內容離得太遠，我們以後也不會用它，因此我們不介紹它，大家可以自己去查。有個名詞在這里的話找學習資料將變得非常容易，我最怕的就是一個東西不知道叫什麼名字，半天找不到資料。

歸並排序有一個有趣的副產品。利用歸並排序能夠在O(nlogn)的時間里計算出給定序列里逆序對的個數。你可以用任何一種平衡二叉樹來完成這個操作，但用歸並排序統計逆序對更方便。我們討論逆序對一般是說的一個排列中的逆序對，因此這里我們假設所有數不相同。假如我們想要數1, 6, 3, 2, 5, 4中有多少個逆序對，我們首先把這個數列分為左右兩段。那麼一個逆序對只可能有三種情況：兩個數都在左邊，兩個數都在右邊，一個在左一個在右。在左右兩段分別處理完後，線性合並的過程中我們可以順便算出所有第三種情況的逆序對有多少個。換句話說，我們能在線性的時間里統計出A隊列的某個數比B隊列的某個數大有多少種情況。

A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6 A隊列：1 3 6
B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ==> B隊列：2 4 5 ……
輸出： 輸出：1 輸出：1 2 輸出：1 2 3 輸出：1 2 3 4

每一次從B隊列取出一個數時，我們就知道了在A隊列中有多少個數比B隊列的這個數大，它等於A隊列現在還剩的數的個數。比如，當我們從B隊列中取出2時，我們同時知道了A隊列的3和6兩個數比2大。在合並操作中我們不斷更新A隊列中還剩幾個數，在每次從B隊列中取出一個數時把當前A隊列剩的數目加進最終答案里。這樣我們算出了所有「大的數在前一半，小的數在後一半」的情況，其餘情況下的逆序對在這之前已經被遞歸地算過了。

============================華麗的分割線============================

堆排序(Heap Sort)利用了堆(Heap)這種數據結構（什麼是堆？）。堆的插入操作是平均常數的，而刪除一個根節點需要花費O(log n)的時間。因此，完成堆排序需要線性時間建立堆（把所有元素依次插入一個堆），然後用總共O(nlogn)的時間不斷取出最小的那個數。只要堆會搞，堆排序就會搞。堆在那篇日誌里有詳細的說明，因此這里不重復說了。

============================華麗的分割線============================

快速排序(Quick Sort)也應用了遞歸的思想。我們想要把給定序列分成兩段，並對這兩段分別進行排序。一種不錯的想法是，選取一個數作為「關鍵字」，並把其它數分割為兩部分，把所有小於關鍵字的數都放在關鍵字的左邊，大於關鍵字的都放在右邊，然後遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往後找找到比關鍵字大的，一個從後往前找到比關鍵字小的，然後兩個指針對應的元素交換位置並繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。快速排序是我們最常用的代碼之一，網上的快速排序代碼五花八門，各種語言，各種風格的都有。大家可以隨便找一個來看看，我說過了我們講演算法但不講如何實現。NOIp很簡單，很多人NOIp前就背了一個快速排序代碼就上戰場了。當時我把快速排序背完了，抓緊時間還順便背了一下歷史，免得晚上聽寫又不及格。
不像歸並排序，快速排序的時間復雜度很難計算。我們可以看到，歸並排序的復雜度最壞情況下也是O(nlogn)的，而快速排序的最壞情況是O(n^2)的。如果每一次選的關鍵字都是當前區間里最大（或最小）的數，那麼這樣將使得每一次的規模只減小一個數，這和插入排序、選擇排序等平方級排序沒有區別。這種情況不是不可能發生。如果你每次選擇關鍵字都是選擇的該區間的第一個數，而給你的數據恰好又是已經有序的，那你的快速排序就完蛋了。顯然，最好情況是每一次選的數正好就是中位數，這將把該區間平分為兩段，復雜度和前面討論的歸並排序一模一樣。根據這一點，快速排序有一些常用的優化。比如，我們經常從數列中隨機取一個數當作是關鍵字（而不是每次總是取固定位置上的數），從而盡可能避免某些特殊的數據所導致的低效。更好的做法是隨機取三個數並選擇這三個數的中位數作為關鍵字。而對三個數的隨機取值反而將花費更多的時間，因此我們的這三個數可以分別取數列的頭一個數、末一個數和正中間那個數。另外，當遞歸到了一定深度發現當前區間里的數只有幾個或十幾個時，繼續遞歸下去反而費時，不如返回插入排序後的結果。這種方法同時避免了當數字太少時遞歸操作出錯的可能。

下面我們證明，快速排序演算法的平均復雜度為O(nlogn)。不同的書上有不同的解釋方法，這里我選用演算法導論上的講法。它更有技巧性一些，更有趣一些，需要轉幾個彎才能想明白。
看一看快速排序的代碼。正如我們提到過的那種分割方法，程序在經過若干次與關鍵字的比較後才進行一次交換，因此比較的次數比交換次數更多。我們通過證明一次快速排序中元素之間的比較次數平均為O(nlogn)來說明快速排序演算法的平均復雜度。證明的關鍵在於，我們需要算出某兩個元素在整個演算法過程中進行過比較的概率。
我們舉一個例子。假如給出了1到10這10個數，第一次選擇關鍵字7將它們分成了{1,2,3,4,5,6}和{8,9,10}兩部分，遞歸左邊時我們選擇了3作為關鍵字，使得左部分又被分割為{1,2}和{4,5,6}。我們看到，數字7與其它所有數都比較過一次，這樣才能實現分割操作。同樣地，1到6這6個數都需要與3進行一次比較（除了它本身之外）。然而，3和9決不可能相互比較過，2和6也不可能進行過比較，因為第一次出現在3和9，2和6之間的關鍵字把它們分割開了。也就是說，兩個數A(i)和A(j)比較過，當且僅當第一個滿足A(i)<=x<=A(j)的關鍵字x恰好就是A(i)或A(j) （假設A(i)比A(j)小）。我們稱排序後第i小的數為Z(i)，假設i<j，那麼第一次出現在Z(i)和Z(j)之間的關鍵字恰好就是Z(i)或Z(j)的概率為2/(j-i+1)，這是因為當Z(i)和Z(j)之間還不曾有過關鍵字時，Z(i)和Z(j)處於同一個待分割的區間，不管這個區間有多大，不管遞歸到哪裡了，關鍵字的選擇總是隨機的。我們得到，Z(i)和Z(j)在一次快速排序中曾經比較過的概率為2/(j-i+1)。
現在有四個數，2,3,5,7。排序時，相鄰的兩個數肯定都被比較過，2和5、3和7都有2/3的概率被比較過，2和7之間被比較過有2/4的可能。也就是說，如果對這四個數做12次快速排序，那麼2和3、3和5、5和7之間一共比較了12*3=36次，2和5、3和7之間總共比較了8*2=16次，2和7之間平均比較了6次。那麼，12次排序中總的比較次數期望值為36+16+6=58。我們可以計算出單次的快速排序平均比較了多少次：58/12=29/6。其實，它就等於6項概率之和，1+1+1+2/3+2/3+2/4=29/6。這其實是與期望值相關的一個公式。
同樣地，如果有n個數，那麼快速排序平均需要的比較次數可以寫成下面的式子。令k=j-i，我們能夠最終得到比較次數的期望值為O(nlogn)。

這里用到了一個知識：1+1/2+1/3+...+1/n與log n增長速度相同，即∑(1/n)=Θ(log n)。它的證明放在本文的最後。

在三種O(nlogn)的排序演算法中，快速排序的理論復雜度最不理想，除了它以外今天說的另外兩種演算法都是以最壞情況O(nlogn)的復雜度進行排序。但實踐上看快速排序效率最高（不然為啥叫快速排序呢），原因在於快速排序的代碼比其它同復雜度的演算法更簡潔，常數時間更小。

快速排序也有一個有趣的副產品：快速選擇給出的一些數中第k小的數。一種簡單的方法是使用上述任一種O(nlogn)的演算法對這些數進行排序並返回排序後數組的第k個元素。快速選擇(Quick Select)演算法可以在平均O(n)的時間完成這一操作。它的最壞情況同快速排序一樣，也是O(n^2)。在每一次分割後，我們都可以知道比關鍵字小的數有多少個，從而確定了關鍵字在所有數中是第幾小的。我們假設關鍵字是第m小。如果k=m，那麼我們就找到了答案——第k小元素即該關鍵字。否則，我們遞歸地計算左邊或者右邊：當k<m時，我們遞歸地尋找左邊的元素中第k小的；當k>m時，我們遞歸地尋找右邊的元素中第k-m小的數。由於我們不考慮所有的數的順序，只需要遞歸其中的一邊，因此復雜度大大降低。復雜度平均線性，我們不再具體證了。
還有一種演算法可以在最壞O(n)的時間里找出第k小元素。那是我見過的所有演算法中最沒有實用價值的演算法。那個O(n)只有理論價值。

============================華麗的分割線============================

我們前面證明過，僅僅依靠交換相鄰元素的操作，復雜度只能達到O(n^2)。於是，人們嘗試交換距離更遠的元素。當人們發現O(nlogn)的排序演算法似乎已經是極限的時候，又是什麼制約了復雜度的下界呢？我們將要討論的是更底層的東西。我們仍然假設所有的數都不相等。
我們總是不斷在數與數之間進行比較。你可以試試，只用4次比較絕對不可能給4個數排出順序。每多進行一次比較我們就又多知道了一個大小關系，從4次比較中一共可以獲知4個大小關系。4個大小關系共有2^4=16種組合方式，而4個數的順序一共有4!=24種。也就是說，4次比較可能出現的結果數目不足以區分24種可能的順序。更一般地，給你n個數叫你排序，可能的答案共有n!個，k次比較只能區分2^k種可能，於是只有2^k>=n!時才有可能排出順序。等號兩邊取對數，於是，給n個數排序至少需要log2(n!)次。注意，我們並沒有說明一定能通過log2(n!)次比較排出順序。雖然2^5=32超過了4!，但這不足以說明5次比較一定足夠。如何用5次比較確定4個數的大小關系還需要進一步研究。第一次例外發生在n=12的時候，雖然2^29>12!，但現已證明給12個數排序最少需要30次比較。我們可以證明log(n!)的增長速度與nlogn相同，即log(n!)=Θ(nlogn)。這是排序所需要的最少的比較次數，它給出了排序復雜度的一個下界。log(n!)=Θ(nlogn)的證明也附在本文最後。
這篇日誌的第三題中證明log2(N)是最優時用到了幾乎相同的方法。那種「用天平稱出重量不同的那個球至少要稱幾次」一類題目也可以用這種方法來解決。事實上，這里有一整套的理論，它叫做資訊理論。資訊理論是由香農(Shannon)提出的。他用對數來表示信息量，用熵來表示可能的情況的隨機性，通過運算可以知道你目前得到的信息能夠怎樣影響最終結果的確定。如果我們的信息量是以2為底的，那資訊理論就變成信息學了。從根本上說，計算機的一切信息就是以2為底的信息量(bits=binary digits)，因此我們常說香農是數字通信之父。資訊理論和熱力學關系密切，比如熵的概念是直接從熱力學的熵定義引申過來的。和這個有關的東西已經嚴重偏題了，這里不說了，有興趣可以去看《資訊理論與編碼理論》。我對這個也很有興趣，半懂不懂的，很想了解更多的東西，有興趣的同志不妨加入討論。物理學真的很神奇，利用物理學可以解決很多純數學問題，我有時間的話可以舉一些例子。我他媽的為啥要選文科呢。
後面將介紹的三種排序是線性時間復雜度，因為，它們排序時根本不是通過互相比較來確定大小關系的。

附1：∑(1/n)=Θ(log n)的證明
首先我們證明，∑(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/2，使得兩個1/2加起來湊成一個1；再把1/5,1/6和1/7全部變成1/4，這樣四個1/4加起來又是一個1。我們把所有1/2^k的後面2^k-1項全部擴大為1/2^k，使得這2^k個分式加起來是一個1。現在，1+1/2+...+1/n裡面產生了幾個1呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的擴大後原式各項總和為log n。O(logn)是∑(1/n)的復雜度上界。
然後我們證明，∑(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+...中，我們把1/3變成1/4，使得兩個1/4加起來湊成一個1/2；再把1/5,1/6和1/7全部變成1/8，這樣四個1/8加起來又是一個1/2。我們把所有1/2^k的前面2^k-1項全部縮小為1/2^k，使得這2^k個分式加起來是一個1/2。現在，1+1/2+...+1/n裡面產生了幾個1/2呢？我們只需要看小於n的數有多少個2的冪即可。顯然，經過數的縮小後原式各項總和為1/2*logn。Ω(logn)是∑(1/n)的復雜度下界。

附2：log(n!)=Θ(nlogn)的證明
首先我們證明，log(n!)=O(nlogn)。顯然n!<n^n，兩邊取對數我們得到log(n!)<log(n^n)，而log(n^n)就等於nlogn。因此，O(nlogn)是log(n!)的復雜度上界。
然後我們證明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)....1，把前面一半的因子全部縮小到n/2，後面一半因子全部捨去，顯然有n!>(n/2)^(n/2)。兩邊取對數，log(n!)>(n/2)log(n/2)，後者即Ω(nlogn)。因此，Ω(nlogn)是log(n!)的復雜度下界。

今天寫到這里了，大家幫忙校對哦
Matrix67原創
轉貼請註明出處

『貳』 常見的幾種排序演算法總結

對於非科班生的我來說，演算法似乎對我來說是個難點，查閱了一些資料，趁此來了解一下幾種排序演算法。
首先了解一下，什麼是程序

關於排序演算法通常我們所說的往往指的是內部排序演算法，即數據記錄在內存中進行排序。
排序演算法大體可分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序等。
另一種是非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等

冒泡排序它重復地走訪過要排序的元素，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個演算法的名字由來是因為越小(或越大)的元素會經由交換慢慢「浮」到數列的頂端。

選擇排序類似於冒泡排序，只不過選擇排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾，以此類推，直到所有元素均排序完畢。

插入排序比冒泡排序和選擇排序更有效率，插入排序類似於生活中抓撲克牌來。
插入排序具體演算法描述，以數組[3, 2, 4, 5, 1]為例。

前面三種排序演算法只有教學價值，因為效率低，很少實際使用。歸並排序（Merge sort）則是一種被廣泛使用的排序方法。
它的基本思想是，將兩個已經排序的數組合並，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然後不斷地兩兩合並，直到全部排序完成。
以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半隻包含零個元素或一個元素為止，然後就用merge函數，將拆成兩半的數組不斷合並，直到合並成一整個排序完成的數組。

快速排序（quick sort）是公認最快的排序演算法之一，有著廣泛的應用。
快速排序演算法步驟

參考：
常用排序演算法總結(一)
阮一峰-演算法總結

『叄』 歸並排序演算法原理

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono"弊租培,"lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序演算法是《數據結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內型答部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。以下是歸並排序演算法：

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

作為一種典型的分而治之思想的演算法應用，歸並排序的實現由兩種方法：
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）； 自下租唯而上的迭代；
在《數據結構與演算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對於遞歸法，作者卻認為：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中這種方式不太可行，因為這個演算法的遞歸深度對它來講太深了。

說實話，我不太理解這句話。意思是 JavaScript 編譯器內存太小，遞歸太深容易造成內存溢出嗎？還望有大神能夠指教。

和選擇排序一樣，歸並排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內存空間。
2. 演算法步驟
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

重復步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復制到合並序列尾。
3. 動圖演示
代碼實現 JavaScript 實例 function mergeSort ( arr ) {   // 採用自上而下的遞歸方法
    var len = arr. length ;
    if ( len

『肆』 歸並排序演算法是什麼

歸並排序演算法定義如下：

歸並排序演算法就是利用分治思想將數組分成兩個小組A，B，再將A，B小組各自分成兩個小組，依次類推，直到分出來的小組只有一個數據時，可以認為這個小組已經是有序的了，然後再合並相鄰的二個小組就可以了。這樣通過先遞歸的分解數組，再合並數組，就完成了歸並排序。

歸並排序演算法特點：

由於歸並排序在歸並過程中需要與原始記錄序列同樣數量的存儲空間存放歸並結果以及遞歸時深度為log2n(2為底)的棧空間。

因此空間復雜度為O(n+logn)，Merge函數中if(SR[i] < SR[j])語句說明需要兩兩比較，不存在跳躍，因此歸並排序是一種穩定的排序演算法，歸並排序是一種比較佔用內存，但卻效率高且穩定的演算法。

『伍』 1,請簡述歸並排序演算法的基本思想;假設有如下數列:50 ,31, 28, 19, 56, 45, 11, 8,

把待排序的數組分成兩組
遞歸排序鋒廳每個數組使數組有序
合並兩個有序數組
50 ,31, 28, 19, 56, 45, 11, 8,
每個數單獨作為一組有序
一次合並
31 50 19 28 45 56 8 11
二次合棗伏並
19 28 31 50 8 11 45 56
三次銀岩隱合並
8 11 19 28 31 45 50 56

『陸』 歸並排序的演算法原理是什麼

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，歸並排序將兩個已排序的表合並成一個表。
歸並排序基本原理

通過對若干個有序結點序列的歸並來實現排序。
所謂歸並是指將若干個已排好序的部分合並成一個有序的部分。

歸並排序基本思想

設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合並到一個局部的暫存序列 temp (相當於輸出序列)中，待合並完成後將 temp 復制回 array[low..high]中，從而完成排序。

在具體的合並過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然後將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩餘記錄依次復制到 array 中即可。

『柒』 軍刀合並演算法是什麼

軍刀合並演算法（Mergesort）是一種基友拍於分治思想的常見排序悉告衫演算法。它將待排序的數組從中間分成兩個子數組，然後對每個子數組遞歸地應用歸並排序演算法，最終將兩個有序子數組合並為一個有序的數組。
具體實現過程如下：
1.將待排序數組從中間分成兩個子數組；
2.對左右兩個子數組進行遞歸操作，直到每個子數組只剩下一個元素；
3.將相鄰的子數組進行合並，形成新的有序子數組，直到整個數組排好序為止。
該演算法時間復睜腔雜度為O(nlogn)，雖然時間復雜度較好，但空間復雜度較高，需要額外的存儲空間來存儲臨時數據。

『捌』 常見排序演算法歸納

排序演算法一般分類：

比較兩個相鄰的元素，將值大的元素交換至右端。

依次比較兩個相鄰的數，將小數放到前面，大數放到後面

即在第一趟：首先比較第1個數和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此一直繼續下去，直到比較最後兩個數，將小數放前，大數放後。然後重復第一趟步驟，直到所有排序完成。

第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較。

第二趟完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較。

依次類推......

輸出結果：

冒泡排序的優點： 每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之後，排在最後的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最後一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數後面，第三趟比較的時候，只需要比較除了最後兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了演算法的量。

用時間復雜度來說：

從一個數組中隨機選出一個數N，通過一趟排序將數組分割成三個部分，1、小於N的區域 2、等於N的區域 3、大於N的區域，然後再按照此方法對小於區的和大於區分別遞歸進行，從而達到整個數據變成有序數組。

如下圖：

假設最開始的基準數據為數組的第一個元素23，則首先用一個臨時變數去存儲基準數據，即 tmp=23 ，然後分別從數組的兩端掃描數組，設兩個指示標志： low 指向起始位置， high 指向末尾。

首先從後半部分開始，如果 掃描到的值大於基準數據 就讓 high-1 ，如果發現有元素比該基準數據的值小，比如上面的 18 <= tmp ，就讓 high位置的值賦值給low位置 ，結果如下：

然後開始從前往後掃描，如果掃描到的值小於基準數據就讓 low+1 ，如果發現有元素大於基準數據的值，比如上圖 46 >= tmp ，就再將 low 位置的值賦值給 high 位置的值，指針移動並且數據交換後的結果如下：

然後再開始從前往後遍歷，直到 low=high 結束循環，此時low或者high的下標就是 基準數據23在該數組中的正確索引位置 ，如下圖所示：

這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數據小的都放到基準數的左邊，比基準數大的數都放到基準數的右邊，這樣就找到了該數據在數組中的正確位置。

然後採用遞歸的方式分別對前半部分和後半部分排序，最終結果就是自然有序的了。

輸出結果：

最好情況下快排每次能恰好均分序列，那麼時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。

將一個數據插入到 已經排好序的有序數據 中

第一趟排序：

用數組的第二個數與第一個數( 看成是已有序的數據 )比較

第二趟排序：

用數組的第三個數與已是有序的數據 {2,3} (剛才在第一趟排的)比較

在第二步中：

...

後面依此類推

輸出結果：

選擇排序是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

舉例：數組 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始數據： 5 2 8 4 9 1

最小數據1，把1放在首位，也就是1和5互換位置，

排序結果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的數據 {2 8 4 9 5} 進行比較，2最小，

排序結果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的數據 {8 4 9 5} 進行比較，4最小，8和4交換

排序結果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他數據 {8 9 5} 進行比較，5最小，8和5交換

排序結果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他數據 {9 8} 進行比較，8最小，8和9交換

排序結果： 1 2 4 5 8 9

輸出結果：

歸並排序（merge sort）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

比如我們對 [8,4,5,7,1,3,6,2] 這個數組進行歸並排序，我們首先利用分治思想的「分」將數組拆分。

輸出結果：

『玖』 求歸並排序演算法！

歸並排序。

1.這里，在把數組暫時復制到臨時數組時，將第二個子數組中的順序顛倒了一下。這樣，兩個子數組從兩端開始處理，使得他們互相成為另一個數組的「檢查哨」。 這個方法是由R.Sedgewick發明的歸並排序的優化。

2.在數組小於某一閥值時，不繼續歸並，而直接使用插入排序，提高效率。這里根據Record的結構，將閥值定位 16。

#define THRESHOLD 16

typedef struct _Record{
int data; //數據
int key; //鍵值
}Record;

//供用戶調用的排序 函數
void Sort(Record Array[], Record TempArray, int left, int right){
TwoWayMergeSort(Array, TempArray, left, right);
}

//歸並排序
void TwoWayMergeSort(Record Array[], Record TempArray[],
int left, int right)
{
if(right <= left) return; //如果只含一個元素，直接返回
if( right-left+1 ){ //如果序列長度大於閥值，繼續遞歸
int middle = (left + right)/2;
Sort(Array, TempArray, left, middle); //對左面進行遞歸
Sort(Array, TempArray, left, right, middle); //對右面進行遞歸
Merge(Array, TempArray, left, right, middle); //合並
}
else{
//如果序列長度小於閥值，採用直接插入排序，達到最佳效果
ImproveInsertSorter(&Array[left], right-left+1);
}
}

//歸並過程
void Merge(Record Array[], Record TempArray[],
int left, int right, int middle)
{
int index1, index2; //兩個子序列的起始位置
int k;

復制左邊的子序列
for(int i=1; i<=middle; i++){
TempArray[i] = Array[i];
}

//復制右邊的子序列，但順序顛倒過來
for(int j=1; j<=right-middle; j++){
TempArray[right-j+1] = Array[j+middle];
}

//開始歸並
for(index1=left, index2=right, k=left; k<=right; k++){
if(TempArray[index1].key<TempArray[index2].key){
Array[k] = TempArray[index++];
}
else{
Array[k] = TempArray[index2--];
}
}
}

//當長度小於閥值時 使用的直接插入排序的代碼
void ImproveInsertSorter(Record Array[], int size){
Record TempRecord; //臨時變數

for(int i=1; i<size; i++){
TempRecord = Array[i];
int j = i-1;
//從i開始往前尋找記錄i的正確位置
while(j>=0 && TempRecord.key<Array[j].key){
Array[j+1] = Array[j];
j = j-1;
}

Array[j+1] = TempRecord;
}
}

終於敲完了。。。 第一次回答問題， 只是覺得好玩`

『拾』 常見演算法4、合並(歸並)排序 Merge sort

歸並排序，是創建在歸並操作上的一種有效的排序演算法。演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

假如如我這里有一組數據，歸並排序過程如下：

通俗點來說，就是先分割，再合並。分割的過程中其實可理解為就是以二分法將數組分割成最小單元，然後再按順序合並起來。

1、Python 3 ：

2、PHP：