- 论坛徽章:
- 0
|
3、进一步泛化,在一组随机排列的数中找出第k小的,这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个,时间复杂度和排序算法相同,可以是Θ(nlgn)。这个问题虽然比前两个问题复杂,但它也有平均情况下时间复杂度是Θ(n)的算法,将上一节习题1的快速排序算法稍加修改就可以解决这个问题:
/* 第k小的元素在start和end之间,找出并返回该元素 */
int order_statistic(int start, int end, int k)
{
用partition函数把序列分成两部分,中间的pivot元素是序列中的第i个;
if (k == i)
返回找到的元素;
else if (k > i)
第k小的元素在序列后半部分,找出并返回该元素;
else
第k小的元素在序列前半部分,找出并返回该元素;
}
快速排序<quickSort.cpp>:- #ifndef QUICKSORT_H
- #define QUICKSORT_H
- class quickSort{
- private:
- int * a,LEN;
- public:
- quickSort(int * array,int length):a(array),LEN(length){}
- ~quickSort(){}
- void quicksort(int start,int end);
- int partition(int start,int end);
- };
- int quickSort::partition(int start,int end){
- int pivot=a[start],temp=0;
- int i=start,j=end;
- while(i<j){
- if(a[i]>pivot){
- temp=a[i];
- a[i]=a[j];
- a[j--]=temp;
- }
- else i++;
- }
- if(a[i]>pivot)i--;
- a[start]=a[i];
- a[i]=pivot;
- return i;
- }
- void quickSort::quicksort(int start,int end){
- int mid;
- if(end>start){
- mid=partition(start,end);
- quicksort(start,mid-1);
- quicksort(mid+1,end);
- }
- }
- #endif
复制代码 找数字<t_find.cpp>:- #include <stdio.h>
- #include "quickSort.cpp"
- const int LEN=8;
- int a[]={4,2,12,7,1,10,9,3};
- quickSort t_q(a,LEN);
- int order_statistic(int start,int end,int k){
- int mid=t_q.partition(start,end);
- if(mid==k)return a[k];
- else if(k>mid)order_statistic(mid+1,end,k);
- else order_statistic(start,mid-1,k);
- }
- int main(void){
- printf("%d\n",order_statistic(0,7,1));
- }
复制代码 |
|