歸併排序
出自 MBA智库百科(https://wiki.mbalib.com/)
目錄 |
歸併排序是指將兩個或兩個以上有序的數列（或有序表），合併成一個仍然有序的數列（或有序表）。這樣的排序方法經常用於多個有序的數據文件歸併成一個有序的數據文件。歸併排序的演算法比較簡單。建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。
歸併過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]複製到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]複製到r[k]中，並令j和k分別加上1，如此迴圈下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素複製到r中從下標k到下標t的單元。歸併排序的演算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸併操作合併成有序的區間[s,t]。
歸併排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息儘量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方。
歸併排序也是一種分割處理式的排序演算法，它是由Johnyon Neumann 於1945年提出的。在歸併排序演算法中，將待排序數據看作是一個鏈表序列，每個鏈表(最壞的情況下每個鏈表中只有一個元素)中的數據都已經排好序，然後不斷地將相鄰的鏈表合併為一些較大的鏈表，當所有的鏈表都合併為一個鏈表時，排序過程也就結束了。歸併排序演算法特別適合於對鍵表或其它非數組形式的數據結構進行排序，它還能對無法放入記憶體的數據進行排序；或者被作為一種特定的排序演算法來使用。
- 排序：（速度僅次於快速排序，為穩定排序演算法，一般用於對總體無序，但是各子項相對有序的數列。
- 求逆序對數：具體思路是，在歸併的過程中計算每個小區間的逆序對數，進而計算出大區間的逆序對數（也可以用樹狀數組來求解）。
