歸并排序python

.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 < 2) {? ? ? ? return arr;? ? }? ? var middle = Math.floor(len / 2),? ? ? ? left = arr.slice(0, middle),? ? ? ? right = arr.slice(middle);? ? return merge(mergeSort(left), mergeSort(right));}function merge(left, right){? ? var result = [];? ? while (left.length && right.length) {? ? ? ? if (left[0] <= right[0]) {? ? ? ? ? ? result.push(left.shift());? ? ? ? } else {? ? ? ? ? ? result.push(right.shift());? ? ? ? }? ? }? ? while (left.length)? ? ? ? result.push(left.shift());? ? while (right.length)? ? ? ? result.push(right.shift());? ? return result;}Python實例 def mergeSort(arr):? ? import math? ? if(len(arr)<2):? ? ? ? return arr? ? middle = math.floor(len(arr)/2)? ? left, right = arr[0:middle], arr[middle:]? ? return merge(mergeSort(left), mergeSort(right))def merge(left,right):? ? result = []? ? while left and right:? ? ? ? if left[0] <= right[0]:? ? ? ? ? ? result.append(left.pop(0))? ? ? ? else:? ? ? ? ? ? result.append(right.pop(0));? ? while left:? ? ? ? result.append(left.pop(0))? ? while right:? ? ? ? result.append(right.pop(0));? ? return resultGo 實例 func mergeSort(arr []int) []int {? ? ? ? length := len(arr)? ? ? ? if length < 2 {? ? ? ? ? ? ? ? return arr? ? ? ? }? ? ? ? middle := length / 2? ? ? ? left := arr[0:middle]? ? ? ? right := arr[middle:]? ? ? ? return merge(mergeSort(left), mergeSort(right))}func merge(left []int, right []int) []int {? ? ? ? var result []int? ? ? ? for len(left) != 0 && len(right) != 0 {? ? ? ? ? ? ? ? if left[0] <= right[0] {? ? ? ? ? ? ? ? ? ? ? ? result = append(result, left[0])? ? ? ? ? ? ? ? ? ? ? ? left = left[1:]? ? ? ? ? ? ? ? } else {? ? ? ? ? ? ? ? ? ? ? ? result = append(result, right[0])? ? ? ? ? ? ? ? ? ? ? ? right = right[1:]? ? ? ? ? ? ? ? }? ? ? ? }? ? ? ? for len(left) != 0 {? ? ? ? ? ? ? ? result = append(result, left[0])? ? ? ? ? ? ? ? left = left[1:]? ? ? ? }? ? ? ? for len(right) != 0 {? ? ? ? ? ? ? ? result = append(result, right[0])? ? ? ? ? ? ? ? right = right[1:]? ? ? ? }? ? ? ? return result}Java實例 public class MergeSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝，不改變參數內容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? if (arr.length < 2) {? ? ? ? ? ? return arr;? ? ? ? }? ? ? ? int middle = (int) Math.floor(arr.length / 2);? ? ? ? int[] left = Arrays.copyOfRange(arr, 0, middle);? ? ? ? int[] right = Arrays.copyOfRange(arr, middle, arr.length);? ? ? ? return merge(sort(left), sort(right));? ? }? ? protected int[] merge(int[] left, int[] right) {? ? ? ? int[] result = new int[left.length + right.length];? ? ? ? int i = 0;? ? ? ? while (left.length > 0 && right.length > 0) {? ? ? ? ? ? if (left[0] <= right[0]) {? ? ? ? ? ? ? ? result[i++] = left[0];? ? ? ? ? ? ? ? left = Arrays.copyOfRange(left, 1, left.length);? ? ? ? ? ? } else {? ? ? ? ? ? ? ? result[i++] = right[0];? ? ? ? ? ? ? ? right = Arrays.copyOfRange(right, 1, right.length);? ? ? ? ? ? }? ? ? ? }? ? ? ? while (left.length > 0) {? ? ? ? ? ? result[i++] = left[0];? ? ? ? ? ? left = Arrays.copyOfRange(left, 1, left.length);? ? ? ? }? ? ? ? while (right.length > 0) {? ? ? ? ? ? result[i++] = right[0];? ? ? ? ? ? right = Arrays.copyOfRange(right, 1, right.length);? ? ? ? }? ? ? ? return result;? ? }}PHP實例 function mergeSort($arr){? ? $len = count($arr);? ? if ($len < 2) {? ? ? ? return $arr;? ? }? ? $middle = floor($len / 2);? ? $left = array_slice($arr, 0, $middle);? ? $right = array_slice($arr, $middle);? ? return merge(mergeSort($left), mergeSort($right));}function merge($left, $right){? ? $result = [];? ? while (count($left) > 0 && count($right) > 0) {? ? ? ? if ($left[0] <= $right[0]) {? ? ? ? ? ? $result[] = array_shift($left);? ? ? ? } else {? ? ? ? ? ? $result[] = array_shift($right);? ? ? ? }? ? }? ? while (count($left))? ? ? ? $result[] = array_shift($left);? ? while (count($right))? ? ? ? $result[] = array_shift($right);? ? return $result;}C實例 int min(int x, int y) {? ? return x < y ? x : y;}void merge_sort(int arr[], int len) {? ? int *a = arr;? ? int *b = (int *) malloc(len * sizeof(int));? ? int seg, start;? ? for (seg = 1; seg < len; seg += seg) {? ? ? ? for (start = 0; start < len; start += seg * 2) {? ? ? ? ? ? int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);? ? ? ? ? ? int k = low;? ? ? ? ? ? int start1 = low, end1 = mid;? ? ? ? ? ? int start2 = mid, end2 = high;? ? ? ? ? ? while (start1 < end1 && start2 < end2)? ? ? ? ? ? ? ? b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];? ? ? ? ? ? while (start1 < end1)? ? ? ? ? ? ? ? b[k++] = a[start1++];? ? ? ? ? ? while (start2 < end2)? ? ? ? ? ? ? ? b[k++] = a[start2++];? ? ? ? }? ? ? ? int *temp = a;? ? ? ? a = b;? ? ? ? b = temp;? ? }? ? if (a != arr) {? ? ? ? int i;? ? ? ? for (i = 0; i < len; i++)? ? ? ? ? ? b[i] = a[i];? ? ? ? b = a;? ? }? ? free(b);}

遞歸版：

實例 void merge_sort_recursive(int arr[], int reg[], int start, int end) {? ? if (start >= end)? ? ? ? return;? ? int len = end - start, mid = (len >> 1) + start;? ? int start1 = start, end1 = mid;? ? int start2 = mid + 1, end2 = end;? ? merge_sort_recursive(arr, reg, start1, end1);? ? merge_sort_recursive(arr, reg, start2, end2);? ? int k = start;? ? while (start1 <= end1 && start2 <= end2)? ? ? ? reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];? ? while (start1 <= end1)? ? ? ? reg[k++] = arr[start1++];? ? while (start2 <= end2)? ? ? ? reg[k++] = arr[start2++];? ? for (k = start; k <= end; k++)? ? ? ? arr[k] = reg[k];}void merge_sort(int arr[], const int len) {? ? int reg[len];? ? merge_sort_recursive(arr, reg, 0, len - 1);}C++

迭代版：

實例 template // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能void merge_sort(T arr[], int len) {? ? T *a = arr;? ? T *b = new T[len];? ? for (int seg = 1; seg < len; seg += seg) {? ? ? ? for (int start = 0; start < len; start += seg + seg) {? ? ? ? ? ? int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);? ? ? ? ? ? int k = low;? ? ? ? ? ? int start1 = low, end1 = mid;? ? ? ? ? ? int start2 = mid, end2 = high;? ? ? ? ? ? while (start1 < end1 && start2 < end2)? ? ? ? ? ? ? ? b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];? ? ? ? ? ? while (start1 < end1)? ? ? ? ? ? ? ? b[k++] = a[start1++];? ? ? ? ? ? while (start2 < end2)? ? ? ? ? ? ? ? b[k++] = a[start2++];? ? ? ? }? ? ? ? T *temp = a;? ? ? ? a = b;? ? ? ? b = temp;? ? }? ? if (a != arr) {? ? ? ? for (int i = 0; i < len; i++)? ? ? ? ? ? b[i] = a[i];? ? ? ? b = a;? ? }? ? delete[] b;}

遞歸版：

實例 void Merge(vector &Array, int front, int mid, int end) {? ? // preconditions:? ? // Array[front...mid] is sorted? ? // Array[mid+1 ... end] is sorted? ? // Copy Array[front ... mid] to LeftSubArray? ? // Copy Array[mid+1 ... end] to RightSubArray? ? vector LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);? ? vector RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);? ? int idxLeft = 0, idxRight = 0;? ? LeftSubArray.insert(LeftSubArray.end(), numeric_limits::max());? ? RightSubArray.insert(RightSubArray.end(), numeric_limits::max());? ? // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]? ? for (int i = front; i <= end; i++) {? ? ? ? if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {? ? ? ? ? ? Array[i] = LeftSubArray[idxLeft];? ? ? ? ? ? idxLeft++;? ? ? ? } else {? ? ? ? ? ? Array[i] = RightSubArray[idxRight];? ? ? ? ? ? idxRight++;? ? ? ? }? ? }}void MergeSort(vector &Array, int front, int end) {? ? if (front >= end)? ? ? ? return;? ? int mid = (front + end) / 2;? ? MergeSort(Array, front, mid);? ? MergeSort(Array, mid + 1, end);? ? Merge(Array, front, mid, end);}C#實例 public static List sort(List lst) {? ? if (lst.Count <= 1)? ? ? ? return lst;? ? int mid = lst.Count / 2;? ? List left = new List(); ?// 定義左側List? ? List right = new List(); // 定義右側List? ? // 以下兩個循環把 lst 分為左右兩個 List? ? for (int i = 0; i < mid; i++)? ? ? ? left.Add(lst[i]);? ? for (int j = mid; j < lst.Count; j++)? ? ? ? right.Add(lst[j]);? ? left = sort(left);? ? right = sort(right);? ? return merge(left, right);}///

/// 合併兩個已經排好序的List///

/// 左側List/// 右側List/// static List merge(List left, List right) {? ? List temp = new List();? ? while (left.Count > 0 && right.Count > 0) {? ? ? ? if (left[0] <= right[0]) {? ? ? ? ? ? temp.Add(left[0]);? ? ? ? ? ? left.RemoveAt(0);? ? ? ? } else {? ? ? ? ? ? temp.Add(right[0]);? ? ? ? ? ? right.RemoveAt(0);? ? ? ? }? ? }? ? if (left.Count > 0) {? ? ? ? for (int i = 0; i < left.Count; i++)? ? ? ? ? ? temp.Add(left[i]);? ? }? ? if (right.Count > 0) {? ? ? ? for (int i = 0; i < right.Count; i++)? ? ? ? ? ? temp.Add(right[i]);? ? }? ? return temp;}Ruby實例 def merge list? return list if list.size < 2? pivot = list.size / 2? # Merge? lambda { |left, right|? ? final = []? ? until left.empty? or right.empty?? ? ? final << if left.first < right.first; left.shift else right.shift end? ? end? ? final + left + right? }.call merge(list[0...pivot]), merge(list[pivot..-1])end

參考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

以下是熱心網友對歸并排序算法的補充，僅供參考：

熱心網友提供的補充1：

分而治之

可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現（也可采用迭代的方式去實現）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

合并相鄰有序子序列

再來看看治階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟。

import java.util.Arrays;

/**
 * Created by chengxiao on 2016/12/8.
 */
public class MergeSort {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一個長度等于原數組長度的臨時數組，避免遞歸中頻繁開辟空間
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left以上為歸并排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括： 
關于時間復雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。
關于穩定性
穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。
不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
n：數據規模
k："桶"的個數
In-place：占用常數內存，不占用額外內存
Out-place：占用額外內存
穩定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同