快速排序求第K个小的数

问题：快速排序求第k小的数，思想非常简单，就是如果要查找的k比当前下标i小，则只递归左部分，大或相等则递归右部分。当然由于数组下标从0开始，所以应该是k-1（比如第一大的数数组下标为0)。原理就是快速排序是以一个元素为分隔的，如果求第k大的元素，也就是求第n-k+1小的元素。
1、阐述原理

快速排序的思想：将数组中某一个元素m作为划分依据（我们假设为第一个元素，即m = arr[0]），遍历一遍数组，使得数组的格局变成这样的三个部分：
（1）m前面的元素
（2）m
（3）m后面的元素。
其中m前面的元素小于m，m后面的元素大于m，这样找第k小的数正好可以借鉴这个思想，即：
①若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中搜索第k小的数；
②若m前面的元素个数小于k，则第k小的数一定在m后面的元素中，这是我们只需要继续在m后面的元素中搜索第k-s小的数，其中s是m前面的元素个数。
2、代码展示

#include<stdio.h>
void main(){
         int a[]={2,4,3,5,6,7,9,8,10,1};
         int k=6;
        printf("the %d least number is %d\n", k, qucikSelect(a, 0, sizeof(a)/sizeof(int)-1,k));
}
int qucikSelect(int a[], int s, int t, int k){
     int tmp=a[s];        //s是最开始的位置，作为start
     int i = s;
     int j = t;           //作为end
     if (s < t){
          while(i !=j){
                  while(j > i  && a[j]>tmp)
                         j--;         //如果满足j>i,并且a[j]>temp,则将end前移一个
                       a[i]=a[j];     //如果不满足，则交换元素位置
                   while(j > i && a[i] < tmp)
                       i++;             //如果满足j>i,并且a[i]<temp,则将start后移一个
                        a[j]=a[i];       //如果不满足，则交换元素位置
     }
     a[i]=tmp;        //将基数赋temp赋给a[i]
     if(i == k-1) return a[i];  //如果第i个数刚好是第k个数，则返回a[i]
     else if(i > k-1){ return qucikSelect(a, s, i-1, k);}//如果temp前面的数大于K，则在左边进行递归
     else if(i < k-1){return qucikSelect(a, i+1,t, k);}//如果temp前面的数小于K，则在右边进行递归
     }
     else{
            if(s  == t && s == k-1)   //如果s和t指针指到同一个数，且刚好是第k小的数，则返回a[s]
                return a[s];
     }
}

3、测试结果

4、快速排序复杂度分析