Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1750187
  • 博文数量: 152
  • 博客积分: 3730
  • 博客等级: 上尉
  • 技术积分: 3710
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-02 14:36
个人简介

减肥,运动,学习,进步...

文章分类

全部博文(152)

文章存档

2016年(14)

2015年(17)

2014年(16)

2013年(4)

2012年(66)

2011年(35)

分类: C/C++

2012-09-13 17:23:54

    好久没有写博客了,这一段时间主要在准备为将来找工作复习,今天我就总结一下关于如何查找数组的前K个最小值实现方法,查找前K个最小值实现方法很多,主要的思想包括如下的几种:
    1、对数组进行排序,然后前K个元素就是需要查找的元素,排序的方法可以采用快速排序,但是我们知道在快速排序中如果已经是有序的数组,采用快速排序的时间复杂度是O(N^2),为了解决这种问题,通常选择随机选择一个数组值pivot作为基准,将数组分为S1 =< pivot和S2 > pivot,这样就能避免快速排序中存在的问题,或者采用随机选择三个元素,然后取中间值作为基准就能避免快速算法的最差时间复杂度,这种方法的前K个数字是有序的。
 
    2、既然是选择前K个对象,那么就没必要对所有的对象进行排序,可以采用快速选择的思想获得前K个对象,比如首先采用快速排序的集合划分方法划分集合:S1,pivot,S2,然后比较K是否小于S1的个数,如何小于,则直接对S1进行快速排序,如果K的个数超过S1,那么对S2进行快速排序,排序完成之后,取数组的前K个元素就是数组的前K个最小值。这种实现方法肯定比第一种的全快速排序要更快速。
 
    3、将数组转换为最小堆的情况,根据最小堆的特性,第一个元素肯定就是数组中的最小值,这时候我们可以将元素保存起来,然后将最后一个元素提升到第一个元素,重新构建最小堆,这样进行K次的最小堆创建,就找到了前K个最小值,这是运用了最小堆的特性,实质上是最小堆的删除实现方法。这种算法的好处是实现了数组的原地排序,并不需要额外的内存空间。
 
    4、接下来的这种思想有点类似桶排序,首先给定一个K个大小的数组b,然后复制数组a中的前K个数到数组b中,将这K个数当成数组a的前K个最小值,对数组b创建最大堆,这时候再次比较数组a中的其他元素,如果其他元素小于数组b的最大值(堆顶),则将堆顶的值进行替换,并重新创建最大堆。这样遍历一次数组就找到了前K个最小元素。这种方法运用了额外的内存空间,特别当选择的K值比较大时,这种方法有待于权衡一下。
    这种方法对于海量数据来说是有较好的作用,对于海量数据不能全部存放在内存中,这时候创建一个较小的数组空间,然后创建最大堆,从硬盘中读取其他的数据,进而实现前K个数据的查找。
 
    这是比较传统的几种方法,当然还存在其他的选择方式,我在这边就不阐述了,从上面几种方法的可知,查找方法都充分运用了运用了数据结构和算法的特性。因此数据结构的灵活运用对算法的实现有很多的好处。
 
下面是我的实现代码,数组中前K个元素我通过打印的方式实现,并没有保存到新的数组中:

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<assert.h>
  5. #include<time.h>

  6. #define LEN 500000
  7. #define K 100

  8. /*堆的性质*/
  9. #define LEFTSON(i) (2*(i)+1)
  10. #define RIGHTSON(i) (2*((i)+1))
  11. #define PARENT(i) (((i)-1)/2)

  12. void swap(int *a, int *b)
  13. {
  14.         assert(a != NULL && b != NULL);

  15.         if(a != b)
  16.         {
  17.                 *a = *a ^ *b;
  18.                 *b = *a ^ *b;
  19.                 *a = *a ^ *b;
  20.         }
  21. }

  22. int partition(int *a, int left, int right)
  23. {
  24.         int pivot = a[right];
  25.         int i = left;
  26.         int j = left - 1;

  27.         assert(a != NULL);

  28.         for(i = left; i < right; ++ i)
  29.         {
  30.                 if(a[i] < pivot)
  31.                 {
  32.                         ++ j;
  33.                         swap(&a[i],&a[j]);
  34.                 }
  35.         }
  36.         swap(&a[j + 1],&a[right]);
  37.         return (j + 1);
  38. }

  39. void quicksort(int *a, int left, int right)
  40. {
  41.         int i = 0;

  42.         assert(a != NULL);

  43.         if(left < right)
  44.         {
  45.                 i = partition(a,left,right);
  46.                 quicksort(a, left, i - 1);
  47.                 quicksort(a, i + 1, right);
  48.         }
  49. }

  50. int QuickSort(int *a, int size)
  51. {
  52.         assert(a != NULL);
  53.         quicksort(a,0,size-1);
  54. }

  55. void quickselect(int *a, int left, int right, int k)
  56. {
  57.         int i = 0;

  58.         assert(a != NULL && left <= k
  59.                 && left <= right && k <= right);

  60.         if(left < right)
  61.         {
  62.                 i = partition(a, left, right);
  63.                 if(i + 1 <= k)
  64.                         quickselect(a, i + 1 , right, k);
  65.                 else if(i > k)
  66.                         quickselect(a, left, i - 1, k);
  67.         }
  68. }

  69. void QuickSelect(int *a, int size, int k)
  70. {
  71.         assert(a != NULL);
  72.         quickselect(a, 0, size - 1, k);
  73. }

  74. /*最大堆*/
  75. void max_heapify(int *a, int left, int right)
  76. {
  77.         int tmp = 0;
  78.         int child = left;
  79.         int parent = left;

  80.         assert(a != NULL);

  81.         for(tmp = a[parent]; LEFTSON(parent) <= right;parent = child)
  82.         {
  83.                 child = LEFTSON(parent);

  84.                 if(child != right && a[child] < a[child + 1])
  85.                         child ++;

  86.                 if(tmp < a[child])
  87.                         a[parent] = a[child];
  88.                 else /*满足最大堆的特性,直接退出*/
  89.                         break;
  90.         }
  91.         a[parent] = tmp;
  92. }

  93. /*创建最大堆*/
  94. void build_maxheap(int *a, int size)
  95. {
  96.         int i = 0;
  97.         assert(a != NULL);

  98.         for(i = PARENT(size); i >= 0 ; -- i)
  99.                 max_heapify(a,i,size - 1);
  100. }

  101. /*最小堆的实现*/
  102. void min_heapify(int *a, int left, int right)
  103. {
  104.         int child = 0;
  105.         int tmp = 0;
  106.         int parent = left;

  107.         assert(a != NULL);

  108.         for(tmp = a[parent]; LEFTSON(parent) <= right; parent = child)
  109.         {
  110.                 child = LEFTSON(parent);

  111.                 if(child != parent && a[child] > a[child + 1])
  112.                         child ++;

  113.                 if(a[child] < tmp)
  114.                         a[parent] = a[child];
  115.                 else /*满足最小堆的特性,直接退出*/
  116.                         break;
  117.         }
  118.         a[parent] = tmp;
  119. }

  120. /*创建最小堆*/
  121. void build_minheap(int *a, int size)
  122. {
  123.         int i = PARENT(size);

  124.         assert(a != NULL);

  125.         for(; i >= 0; -- i)
  126.                 min_heapify(a, i, size - 1);
  127. }

  128. /*采用快速排序查找*/
  129. void find_Kmin_num_1(int *a , int size, int k)
  130. {
  131.         int i = 0;

  132.         assert(a != NULL);

  133.         QuickSort(a, size);

  134. #if 0
  135.         for(i = 0; i < k ; ++ i)
  136.                 printf("%d\t",a[i]);

  137.         printf("\n");
  138. #endif
  139. }

  140. /*采用快速选择实现*/
  141. void find_Kmin_num_2(int *a, int size, int k)
  142. {
  143.         int i = 0;

  144.         assert(a != NULL);

  145.         QuickSelect(a, size, k);

  146. #if 0
  147.         for(i = 0; i < k ; ++ i)
  148.                 printf("%d\t",a[i]);

  149.         printf("\n");
  150. #endif
  151. }

  152. /*采用最大堆实现*/
  153. void find_Kmin_num_3(int *a, int size, int k)
  154. {
  155.         int i = 0;

  156.         int *b = malloc(sizeof(int)*k);

  157.         assert(a != NULL && b != NULL);

  158.         for(i = 0; i < k; ++ i)
  159.                 b[i] = a[i];

  160.         build_maxheap(b,k);

  161.         for(; i < size; ++ i)
  162.         {
  163.                 if(a[i] < b[0])
  164.                 {
  165.                         b[0] = a[i];
  166. // build_maxheap(b , k);
  167.                         max_heapify(b,0,k - 1);
  168.                 }
  169.         }
  170. #if 0
  171.         for(i = 0; i < k ; ++ i)
  172.                 printf("%d\t",b[i]);

  173.         printf("\n");
  174. #endif
  175. }

  176. /*采用最小堆删除元素的方式实现*/
  177. void find_Kmin_num_4(int *a ,int size, int k)
  178. {
  179.         int i = 0;

  180.         assert(a != NULL);

  181.         build_minheap(a, size - 1);
  182.         for(i = 0; i < k; ++ i)
  183.         {
  184. // printf("%d\t",a[0]);

  185.                 /*删除a[0],释放a[size - 1 - i]*/
  186.                 a[0] = a[size -1 - i];
  187.                 min_heapify(a, 0, size - 2 - i);
  188.         }
  189. // printf("\n");
  190. }

  191. int main()
  192. {
  193.         int a[LEN];
  194.         int b[LEN];
  195.         int c[LEN];
  196.         int d[LEN];

  197.         int i = 0,j = 0;

  198.         clock_t _start;
  199.         double times = 0;

  200.         srand((int)time(NULL));

  201.         for(i = 0; i < LEN; ++ i)
  202.         {
  203.                 a[i] = rand()%(LEN);
  204.                 b[i] = a[i];
  205.                 c[i] = a[i];
  206.                 d[i] = a[i];

  207. // printf("%d\t",a[i]);
  208.         }
  209. // printf("\n");

  210.         _start = clock();
  211.         find_Kmin_num_1(a,LEN,K);
  212.         times = (double)(clock() - _start)/CLOCKS_PER_SEC;
  213.         printf("快速排序的查找需要:%f\n",times);

  214.         _start = clock();
  215.         find_Kmin_num_2(b,LEN,K);
  216.         times = (double)(clock() - _start)/CLOCKS_PER_SEC;
  217.         printf("快速选择的查找需要:%f\n",times);

  218.         _start = clock();
  219.         find_Kmin_num_3(c,LEN,K);
  220.         times = (double)(clock() - _start)/CLOCKS_PER_SEC;
  221.         printf("最大堆的查找需要:%f\n",times);

  222.         _start = clock();
  223.         find_Kmin_num_4(d,LEN,K);
  224.         times = (double)(clock() - _start)/CLOCKS_PER_SEC;
  225.         printf("最小堆的查找需要:%f\n",times);

  226.         return 0;
  227. }
检测算法的性能:

点击(此处)折叠或打开

  1. [gong@Gong-Computer interview]$ gcc -g minKnum.c -o minKnum
  2. [gong@Gong-Computer interview]$ ./minKnum
  3. 快速排序的查找需要:0.130000
  4. 快速选择的查找需要:0.020000
  5. 最大堆的查找需要:0.000000
  6. 最小堆的查找需要:0.010000
从结果可知,快速排序的算法效果最差,而最大堆的效果最好,最小堆的效果其次,但是最大堆运用了额外的内存空间。因此在内存空间限制的情况下,考虑最小堆是比较合适的。但是最大堆的思想确实很精妙的,运用了类似桶排序的性质。
 
为了说明算法能否实现前K个最小值的查找,改变数组大小为50,并打印各个方法完成的情况,查找前10个数据,实验结果如下所示:

点击(此处)折叠或打开

  1. [gong@Gong-Computer interview]$ ./minKnum
  2. 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    
  3. 0    1    1    2    4    4    8    8    9    11    
  4. 快速排序的查找需要:0.000000
  5. 1    9    4    8    4    11    1    8    0    2    
  6. 快速选择的查找需要:0.000000
  7. 11    8    9    4    2    1    8    1    4    0    
  8. 最大堆的查找需要:0.000000
  9. 0    1    1    2    4    4    8    8    9    11    
  10. 最小堆的查找需要:0.000000
从上面的实验结果可知,四种方法都是实现了获得前K个最小元素。

阅读(14241) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

索建伟2014-08-08 10:25:31

高手,受教了