《数据结构与算法之美》09——排序（二）归并排序与快速排序
一、归并排序
要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。如下图：
重点：
归并排序使用的是分治思想。分治，就是分而治之，将一个大问题分解成小的子问题来解决。
分治思想跟递归思想很像，分治算法一般是用递归实现。
分治是一种解决问题的处理思想，递归是一种编程技巧。
回忆一下之前学习递归的编程技巧：分析得出递推公式，然后找到终止条件。
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(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(A[p...r], A[p...q], A[q+1...r]) {
var i := p，j := q+1，k := 0 // 初始化变量i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++等于i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判断哪个子数组中有剩余的数据
var start := i，end := q
if j<=r then start := j, end:=r
// 将剩余的数据拷贝到临时数组tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 将tmp中的数组拷贝回A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}归并排序的性能分析
第一，归并排序是稳定的排序算法吗？
归并排序稳不稳定，关键看merge()函数。合并两个数组时，保证相等元素的前后顺序不变即可。
第二，归并排序的时间复杂度是多少？
不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
定义求解问题a的时间是T(a)，求解问题b、c的时间分别是T(b)和T(c)，可以得到以下递推关系式：
T(a) = T(b) + T(c) + 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^k)=T(1)时，也就是n/2^k=1，得到k=log2n。将代入公式，得到T(n)=Cn+nlog2n。
用大O标记法表示就是O(nlogn)
第三，归并排序的空间复杂度是多少？
递归代码的空间复杂度不像时间复杂度那样累加。
尽管每次合并操作都需要申请额外的内存空间，但合并完成之后，临时开辟的内存空间就被释放掉了。
所以空间复杂度是O(n)。
二、快递排序
快排思路：从排序数组中选择任意一个数据作为privot（分区点），遍历数组（p到r）之间的数据，将小于pivot的放到左边，将大于pivot的放在后边，将pivot放在中间。经过这一步骤，将数组p到r之间的数据分成三个部分：
将上面的过程用递推公式来表示：
递推公式：
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(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
}注：一般pivot选择区间数组的最后一个值。
快速排序的性能分析
第一，快速排序是稳定的排序算法吗？
快排是不稳定的排序算法。在分区操作时，相同元素的先后顺序会改变。
第二，快速排序的时间复杂度是多少？
快排也是用递归来实现，归并排序的公式同样适用于快排。
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1
所以，快排的时间复杂度也是O(nlogn)。
但是，公式成立的前提是每次分区操作选择的pivot都很合适，正好能将大区间对待地一分为二。在极端的情况下，每次选择的pivot，分区都是不均等的，这种情况下，时间复杂度就从O(nlogn)退化为O(n2)。
第三，快速排序的空间复杂度是多少？
快排是原地的排序算法，空间复杂度是O(1)。
三、快排和归并的区别
快排和归并用的都是分治思想，递推公式和递归代码也非常相似，区别在于：
归并排序处理过程是由下到上的。而快排是由上到下的。
归并排序是非原地排序算法（主要原因是合并函数无法在原地执行）。快速排序是原地排序算法（通过设计巧妙的原地分区函数，实现原地排序）。
四、课后思考
现在你有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机?内存只有1GB，你有什么好的解决思路，能“快速”地将这10个日志文件合并吗？
按照日期/小时/分钟来区分（主要看日期有多大），遍历文件，把记录分别记录到对应的文件里，然后再对所有文件逐一排序，最后再把文件按照日期来合并。假如存在文件超过1G的情况，再把文件细分。
每个文件内可以使用快排来进行排序。