用的是隨機(jī)算法。
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)