快速选择算法的目的在于可以以O(n)的时间复杂度来选择一个无序随机数组中第k小(大)的元素，它是根据快速排序算法的思想简化而来的。
快速选择算法同样利用了分治回归策略，由于只需要选择出第k小(大)的元素，因此它在分治之后只需要考虑一边的元素情况。它同样利用了快速排序的分割元素集的思想，随机产生一个枢纽元(pivot)，将小于pivot的分到左边，大于pivot的分到右边，记录pivot的位置(记为pos)，并且判断其位置与选择k个最小(大)元素的大小关系，来确定是从左侧选k个还是从右侧选k-pos个，或是直接选到。
具体实现的C语言代码如下：
#include "stdafx.h" #include<stdio.h> #include<stdlib.h> int divideset(int*a, int n, int pivotind) {//将数组按照pivotind处的值分割，并返回该值最后是在那个位置上 int i, j; int tem; //先交换a[pivot]和最后一个元素 tem = a[pivotind]; a[pivotind] = a[n - 1]; a[n - 1] = tem; i = 0; j = n - 2; while (i < j) { while (a[i] < a[n - 1]) { i++; } while (a[j] > a[n - 1]) { j--; } if (i < j) { tem = a[i]; a[i] = a[j]; a[j] = tem; } } tem = a[i]; a[i] = a[n-1]; a[n-1] = tem; return i; } int quickselect(int* a,int n, int k) { int pos=divideset(a,n, 0); //divideset这个函数所做的事是根据pivot来将有n个元素的数组重新分配，并返回pivot的位置pos。 if (pos == k - 1) { return a[pos]; } else if (pos > k-1) { int* b = (int*)malloc((pos + 1) * sizeof(int)); for (int i = 0;i < pos + 1;i++) { b[i] = a[i]; } return quickselect(b,pos+1 ,k); } else { int* b = (int*)malloc((n-pos) * sizeof(int)); for (int i = 0;i < n-pos;i++) { b[i] = a[pos+i]; } return quickselect(b,n-pos,k - pos); } } int main() { printf("input N and K:"); int i, n, k; scanf_s("%d%d", &n, &k); int* a = (int*)malloc(n * sizeof(int)); for (i = 0;i < n;i++) { scanf_s("%d", &a[i]); } printf("\n"); printf("%d", quickselect(a,n,k)); system("pause"); return 0; }