好久没有写博客了，这一段时间主要在准备为将来找工作复习，今天我就总结一下关于如何查找数组的前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 ",a[i]); 137 printf(" "); 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 ",a[i]); 149 printf(" "); 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 ",b[i]); 173 printf(" "); 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 ",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(" "); 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 ",a[i]); 208 } 209 // printf(" "); 210 _start = clock(); 211 find_Kmin_num_1(a,LEN,K); 212 times = (double)(clock() - _start)/CLOCKS_PER_SEC; 213 printf("快速排序的查找需要:%f ",times); 214 _start = clock(); 215 find_Kmin_num_2(b,LEN,K); 216 times = (double)(clock() - _start)/CLOCKS_PER_SEC; 217 printf("快速选择的查找需要:%f ",times); 218 _start = clock(); 219 find_Kmin_num_3(c,LEN,K); 220 times = (double)(clock() - _start)/CLOCKS_PER_SEC; 221 printf("最大堆的查找需要:%f ",times); 222 _start = clock(); 223 find_Kmin_num_4(d,LEN,K); 224 times = (double)(clock() - _start)/CLOCKS_PER_SEC; 225 printf("最小堆的查找需要:%f ",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