性能分析

分析排序算法的三个问题：

稳定性

关键看merge()：两个有序子数组合并成一个有序数组时。

合并过程中，若A[p…q]和A[q+1…r]之间有值相同的元素，则可像伪代码中那样，先把A[p…q]中的元素放入tmp数组。这就保证值相同的元素，在合并前后的先后顺序不变。所以，归并排序是个稳定排序算法。

时间复杂度

归并排序涉及递归，分析稍有点复杂。

• 递归的适用场景
  一个问题A可分解为多个子问题B、C，则求解问题A即可分解为求解问题B、C。问题BC解决后，再把BC的结果合并成A的结果。

若定义求解问题A的时间是T(A)，可得递推关系式：

T(A) = T(B) + T(C) + P

P = 子问题BC的结果合并成问题A的结果所消耗时间

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

假设对n个元素归排需时间T(n)，分解成两个子数组排序的时间都是T(n/2)。

merge()合并两个有序子数组的时间复杂度是O(n)。

所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

n=1：

T ( 1 ) = C ;

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
     ......

所以归并排序的时间复杂度是O(nlogn)

归排执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度非常稳定，不管最好情况、最坏情况，还是平均情况，都是O(nlogn)

空间复杂度

归并排序的时间复杂度任何情况下都是O(nlogn)，真是个秀儿

但归并排序并未像快排应用广泛，why？

它有个致命点：不是原地排序算法。

归并排序的合并函数，在合并两个有序数组为一个有序数组时，需借助额外存储空间。

递归代码的空间复杂度不能像时间复杂度那样累加。

尽管每次合并操作都需申请额外内存空间，但合并完成后，临时开辟的内存空间就被释放了。任意时刻，CPU只会有一个函数在执行，也就只会有一个临时内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度O(n)。

快速排序算法（Quicksort）

快排也是分治思想。乍看有点像归并排序，但思路完全不同。

思想

排序数组中下标从p到r之间的一组数据，选择p到r间任意一数据为pivot（分区点）。

遍历p~r数据：

• 小于pivot的放到左边
• 大于pivot的放到右边
• pivot放到中间

经过这步后，p~r的数据就被分成三部分：

根据分治、递归，可用递归排序下标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)
}

归并排序有个merge()函数，这有个partition()函数：随机选择一个元素作为pivot（一般可选择p~r区间的最后一个元素），然后对A[p…r]分区，函数返回pivot下标。

若不考虑空间消耗，partition()可写得很简单。申请两个临时数组X、Y，遍历A[p…r]：

• 将＜pivot的元素拷贝到X
• ＞pivot的元素都拷贝到Y
• 最后将X、Y中数据顺序拷贝到A[p…r]

但若按照此思路，partition()需很多额外内存空间，那就不是原地排序算法。若希望快排是原地排序算法，则其空间复杂度得O(1)，partition()就不能占用太多额外内存空间，需在A[p…r]原地完成分区操作。

原地分区函数：

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