k-th Order Statistic算法实现（寻找第k小的数）

 1 /* 从start到end之间找出第k小的元素 */
 2 int order_statistic(int start, int end, int k)
 3 {
 4     用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
 5     if (k == i)
 6         返回找到的元素;
 7     else if (k > i)
 8         从后半部分找出第k-i小的元素并返回;
 9     else
10         从前半部分找出第k小的元素并返回;
11 }

 1 #include <stdio.h>
 2 
 3 #define LEN 7
 4 
 5 int array[LEN] = {49, 38, 65, 97, 76, 13, 27};
 6 
 7 int partition(int start, int end)
 8 {
 9     int pivotkey = array[start];
10 
11     while (start < end)
12     {
13         while (start < end && array[end] >= pivotkey)
14             end--;
15         array[start] = array[end];
16         while (start < end && array[start] <= pivotkey)
17             start++;
18         array[end] = array[start];
19     }
20     array[start] = pivotkey;
21 
22     return start;
23 }
24 
25 void order_statistic(int start, int end, int k)
26 {
27     int mid, i;
28 
29     mid = partition(start, end);
30     i = mid - start + 1; //pivotkey是第几小的
31 
32     if (k == i)
33     {
34         printf("the k-th low is %d\n", array[mid]);
35     }
36     else if (k > i)
37     {
38         order_statistic(mid + 1, end, k - i);
39     }
40     else
41     {
42         order_statistic(start, mid - 1, k);
43     }
44 
45     return;
46 }
47 
48 int main(void)
49 {
50     order_statistic(0, LEN - 1, 3);
51     order_statistic(0, LEN - 1, 4);
52     order_statistic(0, LEN - 1, 5);
53     
54     return 0;
55 }