几种查找数组的前K个最小值的算法
for(i = PARENT(size); i >NT(size); i >= 0 ; -- i)
max_heapify(a,i,size - 1);
}
/*最小堆的实现*/
void min_heapify(int *a, int left, int right)
{
int child = 0;
int tmp = 0;
int parent = left;
assert(a != NULL);
for(tmp = a[parent]; LEFTSON(parent) <= right; parent = child)
{
child = LEFTSON(parent);
if(child != parent && a[child] > a[child + 1])
child ++;
if(a[child] < tmp)
a[parent] = a[child];
else /*满足最小堆的特性,直接退出*/
break;
}
a[parent] = tmp;
}
/*创建最小堆*/
void build_minheap(int *a, int size)
{
int i = PARENT(size);
assert(a != NULL);
for(; i >= 0; -- i)
min_heapify(a, i, size - 1);
}
/*采用快速排序查找*/
void find_Kmin_num_1(int *a , int size, int k)
{
int i = 0;
assert(a != NULL);
QuickSort(a, size);
#if 0
for(i = 0; i < k ; ++ i)
printf("%d ",a[i]);
printf("");
#endif
}
/*采用快速选择实现*/
void find_Kmin_num_2(int *a, int size, int k)
{
int i = 0;
assert(a != NULL);
QuickSelect(a, size, k);
#if 0
for(i = 0; i < k ; ++ i)
printf("%d ",a[i]);
printf("");
#endif
}
/*采用最大堆实现*/
void find_Kmin_num_3(int *a, int size, int k)
{
int i = 0;
int *b = malloc(sizeof(int)*k);
assert(a != NULL && b != NULL);
for(i = 0; i < k; ++ i)
b[i] = a[i];
build_maxheap(b,k);
for(; i < size; ++ i)
{
if(a[i] < b[0])
{
b[0] = a[i];
// build_maxheap(b , k);
max_heapify(b,0,k - 1);
}
}
#if 0
for(i = 0; i < k ; ++ i)
printf("%d ",b[i]);
printf("");
#endif
}
/*采用最小堆删除元素的方式实现*/
void find_Kmin_num_4(int *a ,int size, int k)
{
int i = 0;
assert(a != NULL);
build_minheap(a, size - 1);
for(i = 0; i < k; ++ i)
{
// printf("%d ",a[0]);
/*删除a[0],释放a[size - 1 - i]*/
a[0] = a[size -1 - i];
min_heapify(a, 0, size - 2 - i);
}
// printf("");
}
int main()
{
int a[LEN];
int b[LEN];
int c[LEN];
int d[LEN];
int i = 0,j = 0;
clock_t _start;
doubletimes = 0;
srand((int)time(NULL));
for(i = 0; i < LEN; ++ i)
{
a[i] = rand()%(LEN);
b[i] = a[i];
c[i] = a[i];
d[i] = a[i];
// printf("%d ",a[i]);
}
// printf("");
_start = clock();
find_Kmin_num_1(a,LEN,K);
times = (double)(clock() - _start)/CLOCKS_PER_SEC;
printf("快速排序的查找需要:%f",times);
_start = clock();
find_Kmin_num_2(b,LEN,K);
times = (double)(clock() - _start)/CLOCKS_PER_SEC;
printf("快速选择的查找需要:%f",times);
_start = clock();
find_Kmin_num_3(c,LEN,K);
times = (double)(clock() - _start)/CLOCKS_PER_SEC;
printf("最大堆的查找需要:%f",times);
_start = clock();
find_Kmin_num_4(d,LEN,K);
times = (double)(clock() - _start)/CLOCKS_PER_SEC;
printf("最小堆的查找需要:%f",times);
return 0;
}
检测算法的性能:
[gong@Gong-Computer interview]$ gcc -g minKnum.c -o minKnum
[gong@Gong-Computer interview]$ ./minKnum
快速排序的查找需要:0.130000
快速选择的查找需要:0.020000
最大堆的查找需要:0.000000
最小堆的查找需要:0.010000
从结果可知,快速排序的算法效果最差,而最大堆的效果最好,最小堆的效果其次,但是最大堆运用了额外的内存空间。因此在内存空间限制的情况下,考虑最小堆是比较合适的。但是最大堆的思想确实很精妙的,运用了类似桶排序的性质。
为了说明算法能否实现前K个最小值的查找,改变数组大小为50,并打印各个方法完成的情况,查找前10个数据,实验结果如下所示:
[gong@Gong-Computer interview]$ ./minKnum
15 38 14 43 31 45 42 1 32 23 43 34 9 4 45 31 25 48 8 42 40 27 36 30 32 4 11 23 47 12 24 14 1 40 8 32 36 0 35 18 26 28 2 35 35 49 17 12 48 27
0 1 1 2 4 4 8 8 9 11
快速排序的查找需要:0.000000
1 9 4 8 4 11 1 8 0 2
快速选择的查找需要:0.000000
11 8 9 4 2 1 8 1 4 0
最大堆的查找需要:0.000000
0 1 1 2 4 4 8 8 9 11
最小堆的查找需要:0.000000
从上面的实验结果可知,四种方法都是实现了获得前K个最小元素。
查找数组最小值算 相关文章:
- Windows CE 进程、线程和内存管理(11-09)
- RedHatLinux新手入门教程(5)(11-12)
- uClinux介绍(11-09)
- openwebmailV1.60安装教学(11-12)
- Linux嵌入式系统开发平台选型探讨(11-09)
- Windows CE 进程、线程和内存管理(二)(11-09)