选择中位数(第k大的数)

　　在查找中位数时，我们可以先排序，再找中间位置的数值即可，这样时间复杂度是O(nlbn).

　　参考快速排序的分割算法，我们可以得到O(n)复杂度的算法。

　　首先,把问题推广到查找第k小的数，每次分割之后，我们只需要在pivot的一侧查找即可。

 1 #define swap(a, b)    do { int    temp = a; a = b; b = temp; } while (0)
 2 
 3 int partition(int A[], int left, int right)
 4 {
 5     int povit = left;
 6     int l = left, r = right;
 7 
 8     while (l <= r)
 9     {
10         while (l <= right && A[l] <= A[povit])
11             l++;
12         while (r >= left && A[r] > A[povit])
13             r--;
14         if (l < r)
15             swap(A[l], A[r]);
16     }
17     swap(A[povit], A[r]);
18     povit = r;
19     return povit;
20 }
21 
22 int select_kth(int A[], int left, int right, int k)
23 {
24     int povit = left;
25     
26     if (left == right)
27         return A[povit];
28 
29     povit = partition(A, left, right);
30     if (povit - left + 1 >= k)
31         select_kth(A, left, povit, k);
32     else
33         select_kth(A, povit + 1, right, k - (povit - left + 1));
34 }

时间复杂度： T(n) = T(n/2) / 2 + n ==>> T(n) = O(n)