12排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf
《12排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf》由会员分享,可在线阅读,更多相关《12排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf(18页珍藏版)》请在三一文库上搜索。
1、12|排序(下):如何用快排思想在O(n)内查找第K大元素? file:/F/temp/geektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 15:35:29 12|排序(下):如何用快排思想在O(n)内查找第K大元素? 上一节我讲了冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是O(n2),比较高,适合小规模数据的排序。今天,我讲两种时间复杂度 为O(nlogn)的排序算法,归并排序和快速排序。这两种排序算法适合大规模的数据排序,比上一节讲的那三种排序算法要更常用。 归并排序和快速排序都用到了分治思想,非
2、常巧妙。我们可以借鉴这个思想,来解决非排序的问题,比如:如何在O(n)的时间复杂度内查找一个无序数组中的 第K大元素? 这就要用到我们今天要讲的内容。 归并排序的原理 我们先来看归并排序(Merge Sort)。 归并排序的核心思想还是蛮简单的。如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一 起,这样整个数组就都有序了。 12|排序(下):如何用快排思想在O(n)内查找第K大元素? file:/F/temp/geektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 1
3、5:35:29 归并排序使用的就是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。 从我刚才的描述,你有没有感觉到,分治思想跟我们前面讲的递归思想很像。是的,分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想,递归 是一种编程技巧,这两者并不冲突。分治算法的思想我后面会有专门的一节来讲,现在不展开讨论,我们今天的重点还是排序算法。 前面我通过举例让你对归并有了一个感性的认识,又告诉你,归并排序用的是分治思想,可以用递归来实现。我们现在就来看看如何用递归代码来实现归并排 序。 我在第10节讲的递归代码的编写技巧你还记得吗?
4、写递归代码的技巧就是,分析得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。所以,要 想写出归并排序的代码,我们先写出归并排序的递推公式。 递推公式: merge_sort(pr) = merge(merge_sort(pq), merge_sort(q+1r) 终止条件: p = r 不用再继续分解 我来解释一下这个递推公式。 merge_sort(pr)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问题,merge_sort(pq)和merge_sort(q+1r),其中下标q等于p和r的中 间位置,也就是(p+r)/2。当下标从p到q和从q+1到r这两个
5、子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序 了。 12|排序(下):如何用快排思想在O(n)内查找第K大元素? file:/F/temp/geektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 15:35:29 有了递推公式,转化成代码就简单多了。为了阅读方便,我这里只给出伪代码,你可以翻译成你熟悉的编程语言。 / 归并排序算法, A是数组,n表示数组大小 merge_sort(A, n) merge_sort_c(A, 0, n-1) / 递归调用函数 merge_sort
6、_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) / 将Ap.q和Aq+1.r合并为Ap.r merge(Ap.r, Ap.q, Aq+1.r) 你可能已经发现了,merge(Apr, Apq, Aq+1r)这个函数的作用就是,将已经有序的Apq和Aq+1r合并成一个有序的数组,并且放入Apr。那这 个过程具体该如何做呢? 如图所示,我们申请一个临时数组tmp,大小与Apr相同。我们用两个游标i和j
7、,分别指向Apq和Aq+1r的第一个元素。比较这两个元素Ai和Aj,如 果Ai1 通过这个公式,如何来求解T(n)呢?还不够直观?那我们再进一步分解一下计算过程。 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 = 2k * T(n/2k) + k * n 12|排序(下):如何用快排思想在O(n)内查找第K大元素? file:/F/tem
8、p/geektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 15:35:29 通过这样一步一步分解推导,我们可以得到T(n) = 2kT(n/2k)+kn。当T(n/2k)=T(1)时,也就是n/2k=1,我们得到k=log2n 。我们将k值代入上面的公式,得 到T(n)=Cn+nlog2n 。如果我们用大O标记法来表示的话,T(n)就等于O(nlogn)。所以归并排序的时间复杂度是O(nlogn)。 从我们的原理分析和伪代码可以看出,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最
9、好情况、最坏情 况,还是平均情况,时间复杂度都是O(nlogn)。 第三,归并排序的空间复杂度是多少? 归并排序的时间复杂度任何情况下都是O(nlogn),看起来非常优秀。(待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是O(n2)。)但是,归并排 序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法。 这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你,归并排序的空间 复杂度到底是多少呢?是O(n),还是O(nlogn),应该如何分析呢? 如果我们继续按照分析
10、递归时间复杂度的方法,通过递推公式来求解,那整个归并过程需要的空间复杂度就是O(nlogn)。不过,类似分析时间复杂度那样来分析空 间复杂度,这个思路对吗? 实际上,递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点,那就是,尽管每次合并操作都需要申请额外的内存空间,但在合 并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会 超过n个数据的大小,所以空间复杂度是O(n)。 快速排序的原理 我们再来看快速排序算法(Quicksort),我们习惯性把它简称为“快排”。快排利用的也是分
11、治思想。乍看起来,它有点像归并排序,但是思路其实完全不一样。我 们待会会讲两者的区别。现在,我们先来看下快排的核心思想。 快排的思想是这样的:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)。 我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前 面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。 12|排序(下):如何用快排思想在O(n)内查找第K大元素? file:/F/temp/g
12、eektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 15:35:29 根据分治、递归的处理思想,我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩小为1,就说明所有的数据都有序了。 如果我们用递推公式来将上面的过程写出来的话,就是这样: 递推公式: quick_sort(pr) = quick_sort(pq-1) + quick_sort(q+1, r) 终止条件: p = r 我将递推公式转化成递归代码。跟归并排序一样,我还是用伪代码来实现,你可以翻译成你熟悉的任何语言。 12|排序(
13、下):如何用快排思想在O(n)内查找第K大元素? file:/F/temp/geektime/数据结构与算法之美/12排序(下):如何用快排思想在O(n)内查找第K大元素?.html2019/1/15 15:35:29 / 快速排序,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
14、(A, q+1, r) 归并排序中有一个merge()合并函数,我们这里有一个partition()分区函数。partition()分区函数实际上我们前面已经讲过了,就是随机选择一个元素作为pivot(一般 情况下,可以选择p到r区间的最后一个元素),然后对Apr分区,函数返回pivot的下标。 如果我们不考虑空间消耗的话,partition()分区函数可以写得非常简单。我们申请两个临时数组X和Y,遍历Apr,将小于pivot的元素都拷贝到临时数组X,将大 于pivot的元素都拷贝到临时数组Y,最后再将数组X和数组Y中数据顺序拷贝到Apr。 12|排序(下):如何用快排思想在O(n)内查找第K
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 12 排序 何用 思想 查找 元素
链接地址:https://www.31doc.com/p-5529990.html