歸併排序merge sort

歸併排序 (merge sort) 是一類與插入排序、交換排序、選擇排序不同的另一種排序方法。歸併的含義是將兩個或兩個以上的有序表合併成一個新的有序表。歸併排序有

• 多路歸併排序
• 兩路歸併排序 ,

可用於

• 內排序
• 外排序。

這裡僅對內排序的兩路歸併方法進行討論。

1. 演算法思路

1. 把 n 個記錄看成 n 個長度為1的有序子表
2. 進行兩兩歸併使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表
3. 重複第2步直到所有記錄歸併成一個長度為 n 的有序表為止

2. 演算法實現

def merge_sort(unsorted): 返回歸併排序結果 Args: unsorted:未排序的list Return： 排序的list size = len(unsorted) if size == 1: return unsorted middle = size / 2 + size % 2 a = unsorted[:middle] b = unsorted[middle:] a = merge_sort(a) b = merge_sort(b) #進行merge result = [] while a != [] and b != []: if a[0] < b[0]: result.append(a[0]) a.pop(0) else: result.append(b[0]) b.pop(0) result.extend(a) result.extend(b) return resultif __name__ == __main__: a = [1,4,3,2,-10,4,56] print merge_sort(a)

這裡採用了遞歸的方法，每次調用merge_sort都會將當前的未排序的列表進行排序，並進行返回

3. 演算法分析

1. 對長度為 的數據，需要進行 次歸併，而每次歸併的數據量是 ，因此時間複雜度是
2. 歸併排序是一種穩定的排序
3. 需要一個輔助向量來暫存兩有序子文件歸併的結果，故其輔助空間複雜度為 ，顯然它不是就地排序

推薦閱讀：