用的是随机算法。
C代码：
1 #include <stdio.h>
2 #include <stdlib.h>
3 int new_random(int min, int max)
4 {
5 return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
6 }
7 void swap(int *a, int *b)
8 {
9 int c = *a;
10 *a = *b;
11 *b = c;
12 }
13
14 int partition(int A[], int p, int r)
15 {
16 int i = p - 1, j;
17 for(j = p; j < r; j++)
18 {
19 if(A[j] <= A[r])
20 {
21 i++;
22 swap(&A[i], &A[j]);
23 }
24 }
25 swap(&A[i + 1], &A[r]);
26 return i + 1;
27 }
28
29 int randomize_partition(int A[], int p, int r)
30 {
31 int i = new_random(p, r);
32 swap(&A[i], &A[r]);
33 return partition(A, p, r);
34 }
35
36 //第一种算法
37 int randomized_select(int data[], int p, int r, int k)
38 {
39 if(k > (r - p + 1)) return 0;
40 if(p == r) return data[p];
41 int i = randomize_partition(data, p, r);
42 //int i = partition(data, p, r);
43
44 int count = i - p + 1;
45 if(k <= count)
46 return randomized_select(data, p, i, k);
47 else
48 return randomized_select(data, i + 1, r, k - count);
49 }
Java代码：
1 package algorithm;
2
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.List;
6 import java.util.Random;
7
8 public class FindKth {
9
10 public static Random rand = new Random();
11
12 /**
13 * Find the K-th smallest number in a list using random algorithm
14 *
15 * @return the k-th smallest number
16 */
17 public static int selectKth(int[] arr, int k) {
18 int low = 0;
19 int high = arr.length - 1;
20 int m;
21 k = k - 1;
22 while (low < high) {
23 int r = low + rand.nextInt(high - low + 1);
24 swap(arr, low, r);
25 m = low;
26 for (int i = low + 1; i <= high; i++)
27 if (arr[i] < arr[low])
28 swap(arr, ++m, i);
29 swap(arr, low, m);
30 if (m == k)
31 return arr[k];
32 else if (m < k)
33 low = m + 1;
34 else
35 high = m - 1;
36 }
37
38 return arr[k];
39 }
40
41 public static int selectKth(Integer[] arr, int k) {
42 int[] array = new int[arr.length];
43 for (int i = 0; i < arr.length; i++)
44 array[i] = arr[i];
45 return selectKth(array, k);
46 }
47
48 private static void swap(int[] arr, int low, int r) {
49 int tmp = arr[low];
50 arr[low] = arr[r];
51 arr[r] = tmp;
52 }
53
54 /**
55 * @param args
56 */
57 public static void main(String[] args) {
58 List<Integer> list = new ArrayList<Integer>();
59 for (int i = 0; i < 10; i++)
60 list.add(new Integer(i + 1));
61 Integer[] arr = new Integer[list.size()];
62 for (int loop = 0; loop < 1000; loop++) {
63 Collections.shuffle(list);
64 list.toArray(arr);
65 int res = selectKth(arr, 5);
66 if (res != 5)
67 System.out.println(loop + " " + res);
68 }
69
70 }
71
72 }
73
Python代码：
1 #!/usr/bin/env python
2 from random import randint
3
4 # finding the kth smallest number in a list
5 def select(list, k):
6 low = 0
7 up = len(list) - 1
8 k = k - 1
9 while(low < up):
10 rand = randint(low, up)
11 list[low], list[rand] = list[rand], list[low] #swap
12 m = low
13 tmp = list[low]
14 for i in xrange(low + 1, up + 1):
15 if list[i] < tmp:
16 m += 1
17 list[m], list[i] = list[i], list[m] # swap
18 list[m], list[low] = list[low], list[m]
19 if m == k:
20 return list[k]
21 elif m < k:
22 low = m + 1
23 elif m > k:
24 up = m - 1
25 return list[k]
26
27
28 x = range(1, 11)
29 from random import shuffle
30 for i in range(100):
31 shuffle(x)
32 print select(x, 5)