数据结构与算法之美-排序(二)

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

冒泡排序、插入排序、选择排序时间复杂度都是O(n^2)，适合小规模数据的排序。归并排序和快速排序，适合大规模的数据排序，时间复杂度为O(nlogn)，它们都用到了分治思想，可以借鉴这个思想，解决排序问题，比如：如何在 O(n)的时间复杂度内查找一个无序数组中的第 K 大元素？

1. 归并排序

1.1 介绍

核心思想：如果要排序一个数组，先把数组从中间分成前后两个部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。

image.png

分治思想就是将一个大的问题分解成小的子问题来解决，小的问题都解决了，大的问题也就解决了。
分治算法一般都是用递归来实现的，分治是一种解决问题的处理思想，递归是一种编程技巧。

1.2 实现

之前在学习递归时，就是需要先分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码，所以要想写出归并排序，需要先写出归并排序的递推公式：

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

merge_sort(p…r)表示，给下标从p 到 r之间的数组排序，将这个问题转化成两个子问题：merge_sort(p…q),merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是(p+r)/2，当下标从p 到 q 和从q+1到 r这两个子数组都排好序之后，再将两个有序的子数组合并在一起，这样下标从p 到 r 之间的数据也就排好序了。

伪代码如下：

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

merge 函数的作用就是合并两个有序数组，这里就不做介绍了。

1.3 性能分析

• 归并排序是稳定的排序算法，主要在于合并函数中，对于值相等的元素，可以放在前一个数组
• 归并排序的时间复杂度为 O(nlogn)
  问题 a 可以分解为求解问题 b c，问题 a 的时间是 T(a)，问题 b c 的时间分别为 T(b) 和 T(c)，他们的递推关系式如下：

T(a) = T(b) + T(c) + K (K 为合并子问题所消耗的时间)

不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。

归并排序的时间复杂度的计算公式是：

T(1) = C； n=1时，只需要常量级的执行时间，表示为 C
T(n) = 2 * T(n/2) + n; n > 1

// 分解计算过程

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

最终得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1)时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

归并排序的执行效率和排序的原始数组的有序程度无关，所以其时间复杂度很稳定，都是 O(nlogn)。

• 归并排序的空间复杂度为O(n)，不是原地排序算法，因为在合并时，它需要额外的空间去存储合并的有序数组。

2. 快速排序

核心思想：如果要排序数组中下标p 到 r之间的一组数据，可以选择p 到 r之间的任意一个数据作为 pivot(分区点)。

遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot的放到右边，将 pivot 放到中间。经过这一步之后，数组 p 到 r 之间的数据被分成了 3 个部分，前面p 到 q-1 之间都是小于 pivot的，中间是 pivot，后面的q+1到 r之间是大于 pivot 的：

image.png

根据分治、递归的处理思想，可以用递归排序下标从p 到 q-1之间的数据和下标从q+1到 r 之间的数据，直到区间缩小为 1，说明所有的数据都有序了。递推公式如下：

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

伪代码如下：

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

partition 分区函数就是随机选择一个元素作为pivot（一般情况下可以选择 p 到 r 区间的最后一个元素），然后对 A[p...r]分区，函数返回pivot的下标。

如果不考虑空间消耗的话，partition()分区函数可以很简单，申请两个临时数组，将小于和大于 pivot 的元素分别放入这两个数组中：

image.png

但是这样一来，快速排序就不是原地排序算法了，需要很多额外的空间，所以需要改进，伪代码如下：

partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := I+1
    }
  }
  swap A[i] with A[r]
  return I

这里类似于选择排序，通过游标 i 将 A[p...r-1]分成两部分，A[p...i-1]的元素都是小于 pivot 的，暂时称为“已处理区间”，A[i...r-1]为“未处理区间”，每次都从未处理的区间 A[i...r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。这里只需要将 A[i]与 A[j]交换，就可以在 O(1)时间复杂度内将 A[j]放到下标为 i 的位置：

image.png

分区的过程涉及交换操作，所以快速排序不是一个稳定的排序算法。

2.1 性能分析

快排也是用递归实现的，如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式和归并是相同的，都是O(nlogn)。

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1

但是，公式成立的前提是每次分区操作，选择的 pivot 都很合适，正好能将大区间对等的一分为二，实际上这个很难实现。

如果数组中已经是有序了，比如 1 2 5 6 8 ，如果选择将最后一个元素 8作为 pivot，那么每次分区得到的两个区间都是不均等的，需要进行大约 n 次分区操作，每次分区需要扫描大约 n/2个元素，这种情况下，快排的时间复杂度就从 O(nlogn)退化成了 O(n^2)。

快速排序在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。

3. 归并排序和快速排序区别

image.png

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。
快速排序的处理过程是由上到下的，先分区，然后再处理子问题。
归并排序虽然稳定，但是为非原地排序算法，而快速排序虽然不稳定，但是可以实现快速排序，解决了归并排序占用太多内存的问题。

4. 练习

• 归并排序算法
• 快速排序算法
• 寻求无序数组中第 k 大元素，时间复杂度为 O(n)