数据结构与算法之美

学习内容 :排序(下):如何用快排思想在O(n)内查找第K大元素?

时间复杂度为 O(nlogn) 的排序算法,归并排序和快速排序。

归并排序和快速排序都用到了分治思想,非常巧妙.

归并排序(Merge Sort)的原理

归并排序的核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

img

归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突。

要想写出归并排序的代码,我们先写出归并排序的递推公式。

归并排序的性能分析

第一,归并排序是稳定的排序算法吗?归并排序是一个稳定的排序算法。

第二,归并排序的时间复杂度是多少?不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。归并排序的执行效率与要排序的原始数组的有序程度无关,是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn)。

第三,归并排序的空间复杂度是多少?那就是归并排序不是原地排序算法。空间复杂度是 O(n)。

快速排序(Quick Sort)的原理

快排的思想是这样的:如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。

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

img

img

快速排序并不是一个稳定的排序算法。

img

归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法,但是它是非原地排序算法。

快速排序的性能分析

快排是一种原地、不稳定的排序算法。

快排的时间复杂度也是 O(nlogn)。

快排核心思想就是分治和分区