快速排序的一个特点是：每一次分区（partition）操作之后，就有一个元素被放在了数组的最终位置，在以后的排序过程中该元素位置不会变动；
利用这个特点我们可以将快速排序稍加改造来寻找第k个最小值，假设在一次分区操作之后中枢（pivot）的位置在k之前，那么我们下次只需要在中枢的后面进行查找；如果中枢的位置在k之后，那么我们下次只需要在中枢之前进行查找，直到中枢等于k为止。
我们知道快速排序的时间复杂度为O(nlgn)，因为在寻找第k个最小的值时，我们只需要在中枢的一侧进行查找，所以通常来说这个算法的时间复杂度小于O(nlgn)，但是，在最坏情况下这个算法的时间复杂度仍为O(n^2)，比如在原数组有序时如{1,2,3,4,5,6,7,8,9,10…n}，我们在查找第k个最小值的时候，每次中枢的位置都在第一个，而中枢最小，，每次只排除一个元素，假设我们要查找第n/2个最小元素，总的比较次数为:(n-1)+(n-2)+…+(n/2-1)，所以复杂度仍为O(n^2)。
代码实现如下，只需要在原快速排序上做少量改动，想了解快速排序可以看连接快速排序整理分析。
#include<stdio.h>#include<stdlib.h>int partition(int *a,int left,int right){int i = left,j=right;int pivot = a[left];while(i<j){for(;i<j && a[j]>=pivot;j–);a[i] = a[j];for(;i<j && a[i]<=pivot;i++);a[j] = a[i];}a[i] = pivot;return i;}//寻找第k个最小值，k=1,2,…,nint quick_sort(int *a,int left,int right,int k){int split_point;int value;if(left==right){//当left==right时，返回a[left]，这个原快速排序不需要return a[left];}if(left<right){split_point = partition(a,left,right);if(split_point==k-1){ //找到了，返回值return a[split_point];}if(split_point>k-1){//在左侧查找value = quick_sort(a,left,split_point-1,k);}else{<span style="white-space:pre"></span>//在右侧查找value = quick_sort(a,split_point+1,right,k);}}return value;}void main(){int a[] = {11,21,31,14,51,161,7,8,9,10};int value = quick_sort(a,0,9,5);printf("%d",value);printf("\n");}
走走停停，不要害怕错过什么，
