快速排序与求第k大数

发布时间：2020-12-14 03:00:43 所属栏目：大数据来源：网络整理

导读：紫书p227 求第k大数思路：假定在快速排序的“划分”结束后，数组a[p...r]被分成了a[p,q]和a[q+1...r]，则可以根据左边的元素个数q-p+1和k的大小关系只在左边或者只在右边递归求解。可以证明，在期望意义下，程序的时间复杂度为O(n)//我不会证。。

紫书p227

求第k大数思路：

假定在快速排序的“划分”结束后，数组a[p...r]被分成了a[p,q]和a[q+1...r]，则可以根据左边的元素个数q-p+1和k的大小关系只在左边或者只在右边递归求解。

可以证明，在期望意义下，程序的时间复杂度为O(n)//我不会证。。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!