《数据结构与算法之美》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的情况，再把文件细分。

每个文件内可以使用快排来进行排序。