归并排序(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. 动图演示
4. JavaScript 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 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; }
5. Python 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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 result
6. Go 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 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 }
7. Java 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 public class MergeSort implements IArraySort { @Override public int [] sort(int [] sourceArray) throws Exception { 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; } }
8. PHP 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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; }