深入浅出排序算法(2)-归并排序

发表于 | 分类于 ， | | 阅读次数

概述

归并排序是基于分治算法实现的一种排序算法,它将数组分割为两个子数组,然后对子数组进行排序,最终将子数组归并为有序的数组.

归并排序的时间复杂度为O(n log n),空间复杂度为O(1),并且它是稳定的排序算法(所谓稳定即是不影响值相等元素的相对次序).

算法过程

  • 首先,归并排序需要将一个大小为n个元素的数组分解为各包含n/2个元素的子数组(这个分解的过程会不断进行,直到子数组元素个数为1).
  • 当子数组的元素个数为1时,代表这个子数组已经有序,开始两两归并(将两个个数为1的子数组归并为一个个数为2的子数组,不断归并,直到所有子数组个数为2,然后继续将两个个数为2的子数组归并为一个个数为4的子数组….以此类推).
  • 不断重复步骤2,直到整个数组有序.

归并

通过以上的了解,我们发现归并排序中最重要的步骤就是归并.

采用类似洗牌的方式来理解这个过程.想象辅助数组为一个空牌堆,两个子数组为两堆牌a和b.我们从a堆与b堆中各取出一张牌进行比较,然后将较小的牌放入空牌堆中,不断重复比较直到任一牌堆为空.最后,再将未空的牌堆全部放入空牌堆中.

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
// 将两个子序列进行归并
private static void merge(Comparable[] a, int lo, int mid, int hi) {
    Comparable[] aux = new Comparable[a.length]; // 辅助数组
    int i = lo, j = mid + 1;
    int count = lo;
    // 对[lo...mid] 与 [mid+1...hi] 两个子序列的首元素进行比较,将较小的元素放入辅助数组
    while (i <= mid && j <= hi) {
        if (less(a[i], a[j]))
            aux[count++] = a[i++];
        else
            aux[count++] = a[j++];
    }
    //将[lo...mid] 与 [mid+1...hi] 两个子序列中剩余的元素放入辅助数组
    while (i <= mid) {
        aux[count++] = a[i++];
    }
    while (j <= hi) {
        aux[count++] = a[j++];
    }
    // 将辅助数组中的元素复制到源数组中
    for (int k = lo; k <= hi; k++) {
        a[k] = aux[k];
    }
}

递归实现

只要理解了归并的过程,剩下就很容易实现了.归并排序的递归实现如下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  public static void sort(Comparable[] a) {
      sort(a, 0, a.length - 1);
  }
	
  // 递归实现归并排序
  private static void sort(Comparable[] a, int lo, int hi) {
      if (lo >= hi)
          return;
      int mid = (lo + hi) >>> 1; // (lo + hi) / 2
// 分解数组
      sort(a, lo, mid);
      sort(a, mid + 1, hi);
// 归并
      merge(a, lo, mid, hi);
  }

非递归实现

我们已经知道了归并排序中最小子数组的元素个数为1,非递归实现只需要从1开始自底向上地归并即可(递归实现的真实计算过程也是如此,这是由于递归调用是后进先出的).

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
   // 非递归实现归并排序
   private static void sortUnRecursive(Comparable[] a) {
       int len = 1; // 自底向上实现归并排序,子序列的最小粒度为1
       while (len < a.length) {
           for (int i = 0; i < a.length; i += len << 1) {
               merge(a, i, len);
           }
           len = len << 1; // 子序列规模每次迭代时乘2
       }
   }
// 与递归实现的归并函数不同,需要注意边界检查
   private static void merge(Comparable[] a, int lo, int hi) {
       int length = a.length;
       Comparable[] aux = new Comparable[length];
       int count = lo;
       // 子数组1
       int i = lo;
       int i_bound = lo + hi;
       // 子数组2
       int j = i_bound;
       int j_bound = j + hi;
       // 注意j的边界检查
       while (i < i_bound && j < j_bound && j < length) {
           if (less(a[i], a[j]))
               aux[count++] = a[i++];
           else
               aux[count++] = a[j++];
       }
       // i和j都有可能越界
       while (i < i_bound && i < length) {
           aux[count++] = a[i++];
       }
       while (j < j_bound && j < length) {
           aux[count++] = a[j++];
       }
       int k = lo;
       while (k < j && k < length) {
           a[k] = aux[k];
           k++;
       }
   }

本文作者为SylvanasSun(sylvanassun_xtz@163.com),转载请务必指明原文链接.

分享