基于快排的选择算法:就是从数组中随机选一个数,比这个数小的放左边,大的放右边,如果放左边的数的个数等于k-1,说明现在选的这个数就是第k大的数。如果放左边的数的个数大于k个,则递归寻找左边的数组中的第k小的元素,找出的这个数,就是原来数组中的第k大元素。 如果放左边的数的个数小于k个,则在右边的数组当中找第k-p-1小的元素(p为左边数组的大小)。
基于堆的选择算法:维护一个k个元素的最大堆,首先从数组当中取出k个数填入这个堆。然后每次从数组中取出一个元素,和堆顶进行比较。如果比堆顶元素大,则忽略。如果比堆顶元素小,则替换掉堆顶元素,并做一次下滤。
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <algorithm>
#include "windows.h"
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int k;//第k小
const int num = 10000;//数组大小
int testData[num],testData1[num],testData2[num];
//快排方法
int search1(int start, int end , int order){
if (start >= end-1) return testData1[start];
int x = start;
int tmp = rand()%(end-start)+start;
swap(testData1[x],testData1[tmp]);
tmp = testData1[x];
int y = end-1;
while(x < y){
while (x < y && testData1[y] >= tmp){
y--;
}
if (x < y){
testData1[x] = testData1[y];
x++;
}
while (x < y && testData1[x] <= tmp){
x++;
}
if (x < y){
testData1[y] = testData1[x];
y--;
}
}
testData1[x] = tmp;
if (x-start == order-1) return testData1[x];
if (x-start >= order){
return search1(start, x , order);
}
else{
return search1(x+1 , end , order-(x-start)-1 );
}
}
//堆方法
int search2(int start, int end , int order){
make_heap(&testData2[0],&testData2[order],cmp);
for (int i = order ; i < num; i++){
if (testData2[i] < testData2[0]){
pop_heap(&testData2[0],&testData2[order],cmp);
testData2[order-1] = testData2[i];
push_heap(&testData2[0],&testData2[order],cmp);
}
}
return testData2[0];
}
int main(){
srand(time(0));
cout << "k time1 time2"<<endl;
for ( k = 1 ; k < 1000 ;k+=20){
int cc = 1000;
int time1 = 0,time2 = 0;
while(cc--){
for (int i = 0 ; i < num ; i++){
testData[i] = rand()%40000;
testData1[i] = testData[i];
testData2[i] = testData[i];
}
int start_time=GetTickCount();
search1(0,num,k);//快排
int end_time=GetTickCount();
time1 += end_time-start_time;
start_time=GetTickCount();
search2(0,num,k);//最小堆
end_time=GetTickCount();
time2 += end_time-start_time;
}
cout << k << " " << time1 << " "<<time2 << endl;
}
return 0;
}
}
实验结果:
PS:基于快排的算法不稳定,最坏情况是O(n^2)的。在算法导论第9.3节有一个最坏情况为O(n)的选择算法。
版权声明:本文为博主原创文章,未经博主允许不得转载。