归并排序

归并排序(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) 的时间复杂度。代价是需要额外的内存空间。

1. 算法分析

归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤 3 直到某一指针达到序列尾;

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示

动图演示

4. 代码实现

1. JavaScript 代码实现

  1. function mergeSort(arr) { // 采用自上而下的递归方法
  2. var len = arr.length;
  3. if(len < 2) {
  4. return arr;
  5. }
  6. var middle = Math.floor(len / 2),
  7. left = arr.slice(0, middle),
  8. right = arr.slice(middle);
  9. return merge(mergeSort(left), mergeSort(right));
  10. }
  11. function merge(left, right)
  12. {
  13. var result = [];
  14. while (left.length && right.length) {
  15. if (left[0] <= right[0]) {
  16. result.push(left.shift());
  17. } else {
  18. result.push(right.shift());
  19. }
  20. }
  21. while (left.length)
  22. result.push(left.shift());
  23. while (right.length)
  24. result.push(right.shift());
  25. return result;
  26. }

2. Python 代码实现

  1. def mergeSort(arr):
  2. import math
  3. if(len(arr)<2):
  4. return arr
  5. middle = math.floor(len(arr)/2)
  6. left, right = arr[0:middle], arr[middle:]
  7. return merge(mergeSort(left), mergeSort(right))
  8. def merge(left,right):
  9. result = []
  10. while left and right:
  11. if left[0] <= right[0]:
  12. result.append(left.pop(0));
  13. else:
  14. result.append(right.pop(0));
  15. while left:
  16. result.append(left.pop(0));
  17. while right:
  18. result.append(right.pop(0));
  19. return result

3. Go 代码实现

  1. func mergeSort(arr []int) []int {
  2. length := len(arr)
  3. if length < 2 {
  4. return arr
  5. }
  6. middle := length / 2
  7. left := arr[0:middle]
  8. right := arr[middle:]
  9. return merge(mergeSort(left), mergeSort(right))
  10. }
  11. func merge(left []int, right []int) []int {
  12. var result []int
  13. for len(left) != 0 && len(right) != 0 {
  14. if left[0] <= right[0] {
  15. result = append(result, left[0])
  16. left = left[1:]
  17. } else {
  18. result = append(result, right[0])
  19. right = right[1:]
  20. }
  21. }
  22. for len(left) != 0 {
  23. result = append(result, left[0])
  24. left = left[1:]
  25. }
  26. for len(right) != 0 {
  27. result = append(result, right[0])
  28. right = right[1:]
  29. }
  30. return result
  31. }

4. Java 代码实现

  1. public class MergeSort implements IArraySort {
  2. @Override
  3. public int[] sort(int[] sourceArray) throws Exception {
  4. // 对 arr 进行拷贝,不改变参数内容
  5. int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  6. if (arr.length < 2) {
  7. return arr;
  8. }
  9. int middle = (int) Math.floor(arr.length / 2);
  10. int[] left = Arrays.copyOfRange(arr, 0, middle);
  11. int[] right = Arrays.copyOfRange(arr, middle, arr.length);
  12. return merge(sort(left), sort(right));
  13. }
  14. protected int[] merge(int[] left, int[] right) {
  15. int[] result = new int[left.length + right.length];
  16. int i = 0;
  17. while (left.length > 0 && right.length > 0) {
  18. if (left[0] <= right[0]) {
  19. result[i++] = left[0];
  20. left = Arrays.copyOfRange(left, 1, left.length);
  21. } else {
  22. result[i++] = right[0];
  23. right = Arrays.copyOfRange(right, 1, right.length);
  24. }
  25. }
  26. while (left.length > 0) {
  27. result[i++] = left[0];
  28. left = Arrays.copyOfRange(left, 1, left.length);
  29. }
  30. while (right.length > 0) {
  31. result[i++] = right[0];
  32. right = Arrays.copyOfRange(right, 1, right.length);
  33. }
  34. return result;
  35. }
  36. }

5. PHP 代码实现

  1. function mergeSort($arr)
  2. {
  3. $len = count($arr);
  4. if ($len < 2) {
  5. return $arr;
  6. }
  7. $middle = floor($len / 2);
  8. $left = array_slice($arr, 0, $middle);
  9. $right = array_slice($arr, $middle);
  10. return merge(mergeSort($left), mergeSort($right));
  11. }
  12. function merge($left, $right)
  13. {
  14. $result = [];
  15. while (count($left) > 0 && count($right) > 0) {
  16. if ($left[0] <= $right[0]) {
  17. $result[] = array_shift($left);
  18. } else {
  19. $result[] = array_shift($right);
  20. }
  21. }
  22. while (count($left))
  23. $result[] = array_shift($left);
  24. while (count($right))
  25. $result[] = array_shift($right);
  26. return $result;
  27. }