此算法借用快速排序算法。
这个快速选择算法主要利用递归调用，数组存储方式。包含3个文件，头文件QuickSelect.h，库函数QuickSelect.c，测试文件TestQuickSelect。
其中Cutoff可以自己给定，这个当开始给定的数组（或者递归调用产生的子数组）的元素个数<=20个时，采用插入排序。一般认为当元素个数<=20时，插入排序更快。这个20不是固定的，在这附近浮动都可以的。
头文件QuickSelect.h
#ifndef QuickSelect_H
#define QuickSelect_H
#define Cutoff 20
typedef int ElementType;
ElementType Median3(ElementType A[], int left, int right);
void Swap(ElementType *p, ElementType*q);
void InsertionSort(ElementType A[], int N);
ElementType QuickSelect(ElementType A[],int k, int N);
ElementType Qselect(ElementType A[],int k, int Left, int Right);
void PrintMatrix(ElementType A[], int N);
#endif // !QuickSelect_H
库函数QuickSelect.c
#include "QuickSelect.h"
#include<stdio.h>
//通过三数中值分割法获得数组的枢纽元
ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / ;
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
//上述三次交换使得：A[Left]<A[Center]<A[Right]
Swap(&A[Center], &A[Right - ]);
return A[Right - ];//返回枢纽元；
} //交换指针p和q各自指向的值；
void Swap(ElementType * p, ElementType * q)
{
ElementType Tmp;
Tmp = *p;
*p = *q;
*q = Tmp;
} //当开始给定的数组（或者递归调用产生的子数组）的元素个数<=20个时，采用插入排序。
void InsertionSort(ElementType A[], int N)
{
int j, P;
ElementType Tmp;
for (P = ; P < N; P++)
{
Tmp = A[P];
for (j = P; j > && A[j - ] > Tmp; j--)
A[j] = A[j - ];
A[j] = Tmp;
}
} //快速选择算法驱动程序
ElementType QuickSelect(ElementType A[],int k, int N)
{
return Qselect(A, k-, , N - );//该程序即为，输入，k，返回A[k]。因为A从0开始存储，如果想找第5个最小值，其实找的是A[4],所以当我们找第k个值时，应输入k-1。
} //快速选择核心算法
ElementType Qselect(ElementType A[], int k, int Left, int Right)
{
int i, j;
ElementType Pivot;
if (Left + Cutoff - <= Right)//此处Cutoff-1是为了和N-1=Right对应上
{
Pivot = Median3(A, Left, Right);//调用枢纽元函数选取枢纽元
i = Left; j = Right - ;
for (; ;)
{
while (A[++i] < Pivot);
while (A[--j] > Pivot);
if (i < j) Swap(&A[i], &A[j]);
else break;
}
Swap(&A[i], &A[Right - ]);
if (k < i)
Qselect(A, k, Left, i - );//对剩下小于枢纽元的元素递归排序
else if (k>i)
Qselect(A, k, i + , Right);//对剩下大于枢纽元的元素递归排序
//当k=i时，即查询的值==枢纽元，则找到了，返回A[k]
}
else//当最后子数组只有Cutoff个，则采用插入排序。
InsertionSort(A + Left, Right - Left + );
return A[k];
} //打印数组
void PrintMatrix(ElementType A[], int N)
{
for (int i = ; i < N; i++)
printf("%d ", A[i]);
}
测试文件TestQuickSelect
#include "QuickSelect.h"
#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#define N 100000
int main()
{
ElementType A[N] ;
int ID;
srand((unsigned)time(NULL));
for (int i = ; i < N; i++)
{
//A[i] = rand() % N;
A[i] =N-i;//100000个数，倒序排
} printf("\n");
//PrintMatrix(A, N);
printf("请输入要查询的ID:");
scanf_s("%d", &ID);
printf("Result:%d",QuickSelect(A, ID, N));
printf("\n");
}