数据结构与算法之美笔记——排序优化

2019-06-09 本文已影响0人 Cloneable

摘要:

快速排序有普适性、原地算法节省空间的优秀特质，当使用「三点取中」和「随机法」降低快排时间复杂度的退化概率后，快排在底层的排序实现中成为广泛应用的算法。

为何是快排

排序算法多种多样，在之前章节中我们已经学习了常见的几种排序算法，各有特点，我们先对它们进行执行效率的比较。

算法名称	时间复杂度	是否原地	是否稳定
冒泡排序	$O(n^2)$	✔️	✔️
插入排序	$O(n^2)$	✔️	✔️
选择排序	$O(n^2)$	✔️	❌
归并排序	$O(n\log\left(n\right))$	❌	✔️
快速排序	$O(n\log\left(n\right))$	✔️	❌
桶排序	$O(n)$	❌	✔️
计数排序	$O(n)$	❌	✔️
基数排序	$O(n)$	❌	✔️

从图表中来看，桶排序、计数排序和基数排序无疑在时间复杂度上具有较大优势，但这三种算法对排序数据有特殊要求，对于底层排序实现这种需要对数据具有普适性的情况，明显是不适合的。

退而求其次，时间复杂度次之的是归并排序和快速排序，快速排序时间复杂度并不稳定，有退化为 $O(n^2)$ 的可能，而且也不是稳定的排序算法，按理应该选择归并排序，但归并排序有个劣势——不是原地算法。归并排序的空间复杂度是 $O(n)$ ，也就是说当需要排序的数据大小为 100 M 时，还需要额外申请 100 M 的空间，这个缺点导致了快排走上 C 位。

快排的优化

快排虽然走上 C 位，但想成为真正的明星还需要包装一番。快排的时间复杂度并不那么稳定，究其原因是在快排选取分区点时很难理想化地将排序数据均分，当分区极其不平衡时，时间复杂度的退化在所难免，所以要解决快排时间复杂度退化的问题就要解决如何取分区点的问题。

三点取中法

三点取中法就是从排序数据中取三个位置的数据，一般来说是第一个、最后一个和中间一个数据，然后比较三个数据，使用中间的一个数作为分区点数据。这种方法实现简单，但当数据规模较大时，三点可能已经无法满足使分区尽量平衡的要求，需要五点取中甚至十点取中，所以这种方法在遭遇大规模数据时有其弊端。

随机数法

通过随机的方式获取分区点，虽然不能完全避免分区极度不平衡的情况，但能够将这种概率降低，降低时间复杂度退化的可能。

因为算法的实现使用递归的方式，所以快排不仅存在时间复杂度退化的问题，还要避免递归导致的栈内存溢出问题。解决这个问题可以通过限制递归深度，也可以自己在堆上实现方法栈以突破内存限制。

合适的数据遇到合适的算法

虽然使用快排可以实现底层的排序方法，但当数据规模较小时使用快排可能会降低执行效率。虽然 $O(n\log\left(n\right))$ 在时间复杂度的通常意义上来说比 $O(n^2)$ 的更加优秀，但这是忽略常量、系数等的理想情况下，当数据规模较小的时候，常量、系数及低阶项都有影响时间复杂度的可能。

例如， $100+10\log\left(10\right)>10$ 。这样情况肯定会存在，在工业上实现排序方法时，也会对不同的数据规模应用不同类型的排序算法，这样可以提高排序方法的执行效率。

Java 中的应用

Java 中的 Collection 子类就实现了排序方法，我们一起探寻一番平时常用的 List 排序方法的秘密，需要注明此处分析的是 JDK 1.8 源码。

因为 JDK 1.8 引入了 default 关键字，可以允许在 interface 中定义默认的方法实现（感觉 Abstract Class 的功能被削弱），在 List 中有 sort 方法的默认实现。

default void sort(Comparator<? super E> c) {
  Object[] a = this.toArray();
  Arrays.sort(a, (Comparator) c);
  ListIterator<E> i = this.listIterator();
  for (Object e : a) {
    i.next();
    i.set((E) e);
  }
}

Arrays.sort 暴露了其实 List 使用的是 Arrays 的排序方法，继续跟进。

public static <T> void sort(T[] a, Comparator<? super T> c) {
  if (c == null) {
    sort(a);
  } else {
    if (LegacyMergeSort.userRequested)
      legacyMergeSort(a, c);
    else
      TimSort.sort(a, 0, a.length, c, null, 0, 0);
  }
}

LegacyMergeSort.userRequested 来自启动参数 java.util.Arrays.useLegacyMergeSort，可以让用户通过启动参数使用旧的排序方式。默认情况下是使用 TimSort，也是一种排序算法。接着分析一下 legacyMergeSort 方法，毕竟一看名字就知道是我们熟悉的归并排序。

private static void legacyMergeSort(Object[] a) {
  Object[] aux = a.clone();
  mergeSort(aux, a, 0, a.length, 0);
}

private static void mergeSort(Object[] src,
                Object[] dest,
                int low,
                int high,
                int off) {
  int length = high - low;

  // Insertion sort on smallest arrays
  if (length < INSERTIONSORT_THRESHOLD) {
    for (int i=low; i<high; i++)
      for (int j=i; j>low &&
            ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
        swap(dest, j, j-1);
    return;
  }

  // Recursively sort halves of dest into src
  int destLow  = low;
  int destHigh = high;
  low  += off;
  high += off;
  int mid = (low + high) >>> 1;
  mergeSort(dest, src, low, mid, -off);
  mergeSort(dest, src, mid, high, -off);

  // If list is already sorted, just copy from src to dest.  This is an
  // optimization that results in faster sorts for nearly ordered lists.
  if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
    System.arraycopy(src, low, dest, destLow, length);
    return;
  }

  // Merge sorted halves (now in src) into dest
  for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
    if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
      dest[i] = src[p++];
    else
      dest[i] = src[q++];
  }
}

legacyMergeSort 对排序数组克隆之后调用 mergeSort 方法，mergeSort 方法的主体部分和常规的归并排序一样，也是获取中间点，然后分区，分区再进行归并排序，对分区数组合并时进行排序。

int destLow  = low;
int destHigh = high;
low  += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);

// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
  if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
    dest[i] = src[p++];
  else
    dest[i] = src[q++];
}

不过在合并排序的时候增加了一步判断，当前一个分区的最大数不大于后一个分区最小数时两个分区已经自然有序，所以直接按前后顺序拼接两个数组即可，避免了循环比较合并数组。

// If list is already sorted, just copy from src to dest.  This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
  System.arraycopy(src, low, dest, destLow, length);
  return;
}

对于递归的终止条件也进行了不同的处理，当分区数据规模小于 INSERTIONSORT_THRESHOLD （这个常量表示启用插入排序的阀值）时，使用插入排序对数据排序处理并终止递归。

int length = high - low;

// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
  for (int i=low; i<high; i++)
    for (int j=i; j>low &&
          ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
      swap(dest, j, j-1);
  return;
}

总结

快排虽然存在缺点，但使用三点取中法、随机法解决分区不平衡问题，使用限制递归深度、自定义实现方法栈解决递归过深问题后，在实际生产中被广泛应用，不过为了提高排序方法的执行效率一般会根据数据规模的变化采用适合的排序算法。

文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。