找出第k小的数字-期望时间为O(n)-随机选择排序-源码
改正之前随机选择排序的实现：
#include <iostream> #include<ctime>#include<cstdlib>using namespace std; void swap(int &a, int &b) {int temp = a;a = b;b = temp;}int rand(int low, int high) {int size = high - low + 1;return low + rand() % size;}int random_partition(int *a, int low, int high) {int index = rand(low, high);swap(a[index], a[low]);int key = a[low];int i = low;for(int j = low + 1; j <= high; j++) {if(a[j] <= key) {if(i != j) {i = i + 1;swap(a[i], a[j]);}}}swap(a[low], a[i]);return i;}void random_sort(int *a, int low, int high) {if(low < high) {int pivot = random_partition(a, low, high);random_sort(a, low, pivot - 1);random_sort(a, pivot + 1, high);}}int random_select(int *a, int low, int high, int k) {if(k < 1 || k > (high - low + 1))return -1;int pos = random_partition(a, low, high);int m = pos - low + 1;if(m == k) {return a[pos];} else if(k < m) {return random_select(a, low, pos - 1, k);} else {return random_select(a, pos + 1, high, k - m);}}void main() {int a[] = {33, 22, 43, 23, 12, 54, 76, 47, 38, 66};int len = sizeof(a) / sizeof(int);int i;int result = random_select(a, 0, len - 1, 5);//random_sort(a, 0, len - 1);for(i = 0; i < len; i++)cout << a[i] << '\t';cout << "result=" << result << endl;}