昨天讨论的随机化快排对有重复元素的数组会陷入无限循环.今天带来对其的优化,使其支持重复元素. 只需修改partition函数即可: int partition(int *numArray,int head,int tail) { int pivot=numArray[tail]; ; int j=tail; while(true) { do { i++; }while(i<=tail&&numArray[i]<pivot); //找到比主元大的元素 do { j--; }whi
一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量. 一.问题描述 问题:给定一个含有n个元素的无序数组,找出第k小的元素. k = 1 :最小值 k = n :最大值 k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ :中位数 找最大值或最小值很简单,只需要遍历一次数组并记录下最大值或最小值就可以了.我们在这里要解决的问题是一般性的选择问题. 一种原始
从一个序列里面选择第k大的数在没有学习算法导论之前我想最通用的想法是给这个数组排序,然后按照排序结果返回第k大的数值.如果使用排序方法来做的话时间复杂度肯定至少为O(nlgn). 问题是从序列中选择第k大的数完全没有必要来排序,可以采用分治法的思想解决这个问题.Randomize select 算法的期望时间复杂度可以达到O(n),这正是这个算法的迷人之处.具体的算法分析可以在<算法导论>这本书里查看. 贴出伪代码: RANDOMIZED-SELECT(A, p, r, i) if p = r
PS1:如果单纯为做出这道题那么这个代价是O(nlgn),通过排序就可以了. 这里讨论的是O(n)的算法.那么来分析一下这个算法是如何做到O(n)的,算了不分析了,这个推到看起来太麻烦了.其实我想知道的只是结论而已,想感叹的也是partition真是特别好用啊!!!! 代码: #include<iostream> #include<ctime> using namespace std; ; void Swap(int &a, int &b) { int c = a;