《数据结构与算法之美》09——排序(二)归并排序与快速排序

Masimaro 2020-06-21

一、归并排序

要排序一个数组,先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起。如下图:

 《数据结构与算法之美》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),求解问题bc的时间分别是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(分区点),遍历数组(pr)之间的数据,将小于pivot的放到左边,将大于pivot的放在后边,将pivot放在中间。经过这一步骤,将数组pr之间的数据分成三个部分:

 《数据结构与算法之美》09——排序(二)归并排序与快速排序

将上面的过程用递推公式来表示:

递推公式:

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) = Cn=1时,只需要常量级的执行时间,所以表示为C

T(n) = 2*T(n/2) + nn>1

所以,快排的时间复杂度也是O(nlogn)

但是,公式成立的前提是每次分区操作选择的pivot都很合适,正好能将大区间对待地一分为二。在极端的情况下,每次选择的pivot,分区都是不均等的,这种情况下,时间复杂度就从O(nlogn)退化为O(n2)

第三,快速排序的空间复杂度是多少?

快排是原地的排序算法,空间复杂度是O(1)

三、快排和归并的区别

快排和归并用的都是分治思想,递推公式和递归代码也非常相似,区别在于:

归并排序处理过程是由下到上的。而快排是由上到下的。

归并排序是非原地排序算法(主要原因是合并函数无法在原地执行)。快速排序是原地排序算法(通过设计巧妙的原地分区函数,实现原地排序)。

 《数据结构与算法之美》09——排序(二)归并排序与快速排序

四、课后思考

现在你有10个接口访问日志文件,每个日志文件大小约300MB,每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件,合并为1个日志文件,合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机?内存只有1GB,你有什么好的解决思路,能快速地将这10个日志文件合并吗?

按照日期/小时/分钟来区分(主要看日期有多大),遍历文件,把记录分别记录到对应的文件里,然后再对所有文件逐一排序,最后再把文件按照日期来合并。假如存在文件超过1G的情况,再把文件细分。

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

相关推荐