【数据结构与算法】系列二十六 - 快速排序/希尔排序

快速排序的平均时间复杂度和堆排序、归并排序的平均时间复杂度一样都是O(nlogn)，但是快速排序的最坏时间复杂度是O(n^2)。实际上，快速排序的效率比堆排序和归并排序都要快，我们可以通过代码来调节最坏时间复杂度的出现的概率。

一、快速排序

快速排序（Quick Sort）在1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出，昵称为东尼·霍尔(Tony Hoare)。

1.1. 执行流程

从序列中选择一个轴点元素（pivot）；
- 假设每次选择0位置的元素为轴点元素
利用pivot将序列分割成2个子序列；
- 将小于pivot的元素放在pivot前面（左侧）
- 将大于pivot的元素放在pivot后面（右侧）
- 等于pivot的元素放哪边都可以
对子序列进行1、2操作，直到不能再分割（子序列中只剩下1个元素）。

快速排序的本质：逐渐将每一个元素都转换成轴点元素。

1.2. 轴点构造

如上图，begin指向首元素、end指向尾部元素（注意，这里的end和之前排序算法中的end不太一样）。

排序之前，先把首元素（轴点元素）备份，数组中的元素从后往前开始比较
当end指向的元素大于备份的元素时，只需要end--
当end指向的元素小于备份的元素时，end指向的元素覆盖begin指向的位置，并且begin++
当begin指向的元素大于备份的元素时，begin指向的元素覆盖end指向的位置，并且end--
当begin指向的元素小于备份的元素时，只需要begin++
当begin或end指向的元素和备份元素相等时，为了统一步骤，也让他做上面的覆盖操作
当begin和end指向同一个位置时，轴点元素构造完毕，并把备份元素放入这个位置

上面的步骤中，当begin发生覆盖时，下一步取end指向的位置进行比较。当end位置发生覆盖时，下一步取begin指向的位置进行比较。两个交替运行。

注意：轴点把数据分割成了两部分，只要这两部分的begin和end不在同一个位置，都需要再次进行快排（递归）。

1.3. 代码实现

protected void quickSort() {
  sort(0, array.length);
}

/**
 * 对 [begin, end) 范围的元素进行快速排序
 * @param begin
 * @param end
 */
private void sort(int begin, int end) { 
  if (end - begin < 2) return;
  
  // 确定轴点位置 O(n)
  int mid = pivotIndex(begin, end);
  // 对子序列进行快速排序
  sort(begin, mid); 
  sort(mid + 1, end); 
} 

/**
 * 构造出 [begin, end) 范围的轴点元素
 * @return 轴点元素的最终位置
 */
private int pivotIndex(int begin, int end) {
  // 备份begin位置的元素
  int pivot = array[begin];
  // end指向最后一个元素
  end--;
  
  while (begin < end) {
    while (begin < end) {
      if (pivot - array[end] < 0) { // 右边元素 > 轴点元素
        end--;
      } else { // 右边元素 <= 轴点元素
        array[begin++] = array[end];
        break;
      }
    }
    while (begin < end) {
      if (pivot - array[begin] > 0) { // 左边元素 < 轴点元素
        begin++;
      } else { // 左边元素 >= 轴点元素
        array[end--] = array[begin];
        break;
      }
    }
  }
  
  // 将轴点元素放入最终的位置
  array[begin] = pivot;
  // 返回轴点元素的位置
  return begin;
}

1.4. 时间复杂度

在轴点左右元素数量比较均匀的情况下，同时也是最好的情况：T(n) = 2 * T(n/2) + O(n) = O(nlogn)

如果轴点左右元素数量极度不均匀，最坏情况：T(n) = T(n−1) + O(n) = O(n^2)

从下图也可以看出，最坏时间复杂度是三角形面积：

由于右边数据是空的，所以不考虑右边数据排序sort(mid + 1, end)的耗时，只需要考虑左边的排序sort(begin, mid);（即T(n-1)），所以总耗时是T(n) = T(n-1) + O(n)，计算得出（或者对比之前的公式）时间复杂度是O(n^2)。

为了降低最坏情况的出现概率，一般采取的做法是：随机选择轴点元素。

private int pivotIndex(int begin, int end) {
  // 随机选择一个元素跟begin位置进行交换
  int randomIndex = begin + (int)(Math.random() * (end - begin));
  int tmp = array[begin];
  array[begin] = array[randomIndex];
  array[randomIndex] = tmp;
  
  ...

  return begin;
}

最好、平均时间复杂度：O(nlogn)

最坏时间复杂度：O(n^2)

由于递归调用的缘故，空间复杂度：O(logn)

快速排序属于不稳定排序。

1.5. 与轴点相等的元素

如果序列中的所有元素都与轴点元素相等，利用目前的算法实现，轴点元素可以将序列分割成2个均匀的子序列：

思考：比较元素大小的判断分别改为≤、≥ 会起到什么效果？

通过上图的分析可以发现，如果加上条件等于，轴点元素分割出来的子序列极度不均匀，最坏时间复杂度是O(n^2)，效率极大降低。

误区：上面分析的是和轴点元素相等的情况，并不意味着加上等于就是稳定排序，比如上图中如果轴点元素是8，元素...6a...6b...排序后就是...6b...6a...。

二、希尔排序

希尔排序（Shell Sort）在1959年由唐纳德·希尔（Donald Shell）提出。

希尔排序把序列看作是一个矩阵，分成m列，逐列进行排序，m从某个整数逐渐减为1，当m为1时，整个序列将完全有序。因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）。

矩阵的列数取决于步长序列（step sequence），比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序。不同的步长序列，执行效率也不同。

2.1. 实例一

希尔本人给出的步长序列是n/(2^k)，比如n为16时，步长序列是{1, 2, 4, 8}。

1. 分成8列进行排序

2. 分成4列进行排序（在8列排序后的基础上排序）

3. 分成2列进行排序（在4列排序后的基础上排序）

4. 分成1列进行排序（在2列排序后的基础上排序）

思考：最后一次排序只有一列，为什么不直接分成一列呢？前面的3次排序有什么作用呢？

从上面的实例不难看出来，从8列变为1列的过程中，逆序对的数量在逐渐减少。因此希尔排序底层一般使用插入排序对每一列进行排序，也有很多资料认为希尔排序是插入排序的改进版。

2.2. 实例二

假设有11个元素，步长序列是{1, 2, 5}：

假设元素在第col列、第row行，步长（总列数）是step，那么这个元素在数组中的索引是col + row * step。

比如9在排序前是第2列、第0行，那么它排序前的索引是2 + 0 * 5 = 2
比如4在排序前是第2列、第1行，那么它排序前的索引是2 + 1 * 5 = 7

2.3. 代码实现

希尔排序的核心逻辑就是分成多少列，每列进行插入排序（使用插入排序的原因是，后面的排序建立在之前已经排序好的基础上）。

protected void shellSort() {
  List<Integer> stepSequence = shellStepSequence();
  for (Integer step : stepSequence) {
    sort(step);
  }
}

/**
 * 分成step列进行排序
 */
private void sort(int step) {
  // col : 第几列，column的简称
  for (int col = 0; col < step; col++) { // 对第col列进行插入排序
    /*
     注意：这里的核心思想就是换行。

     之前插入排序的begin是从1开始，也就是从原数据的第二个索引开始。

     但是这里的begin不是1，begin是col、col+step、col+2*step、col+3*step（这些数据代表的是每一列）里面的第二个（即col + step）。
     增长条件不是begin++，是begin = begin + step。

     cur - step 指的是上一行的列首数据。
     */ 
    for (int begin = col + step; begin < array.length; begin += step) {
      int cur = begin;
      while (cur > col && cur - (cur - step) < 0) {
        int tmp = array[cur];
        array[cur] = array[cur - step];
        array[cur - step] = tmp;
        cur -= step;
      }
    }
  }
}

/**
 * 获取希尔步长序列（n/(2^k))
 */
private List<Integer> shellStepSequence() {
  List<Integer> stepSequence = new ArrayList<>();
  int step = array.length;
  while ((step >>= 1) > 0) {
    stepSequence.add(step);
  }
  return stepSequence;
}

2.4. 步长序列

希尔本人给出的步长序列，最坏情况时间复杂度是O(n^2)。

private List<Integer> shellStepSequence() {
  List<Integer> stepSequence = new ArrayList<>();
  int step = array.length;
  while ((step >>= 1) > 0) {
    stepSequence.add(step);
  }
  return stepSequence;
}

目前已知的最好的步长序列，最坏情况时间复杂度是O(n^(4/3))，1986年由Robert Sedgewick提出。

当k = 0时，结果是1；
当k = 1时，结果是5；
当k = 2时，结果是19；
当k = 3时，结果是41；
当k = 4时，结果是109；
……

private List<Integer> sedgewickStepSequence() {
  List<Integer> stepSequence = new LinkedList<>();
  int k = 0, step = 0;
  while (true) {
    if (k % 2 == 0) { // 偶数
      int pow = (int) Math.pow(2, k >> 1);
      step = 1 + 9 * (pow * pow - pow);
    } else { // 基数
      int pow1 = (int) Math.pow(2, (k - 1) >> 1);
      int pow2 = (int) Math.pow(2, (k + 1) >> 1);
      step = 1 + 8 * pow1 * pow2 - 6 * pow2;
    }
    if (step >= array.length) break;
    stepSequence.add(0, step);
    k++;
  }
  return stepSequence;
}

不同的步长序列，希尔排序的时间复杂度是不一样的（所以平均时间复杂度取决于步长序列），但是最坏时间复杂度范围是O(n^(4/3)) ~ O(n^2)。因为没有用到额外的存储空间，所以是原地排序，空间复杂度是O(1)，是不稳定排序。在实际开发中也几乎用不到希尔排序，很多底层排序使用频率最高的还是快速排序、归并排序、插入排序等其他排序。