【正确答案】(1)思路
   模拟快速排序的过程。想找出数组a[]中从a[l]到a[r](共r-l+1个元素)的第k个最小值(k≤r-l+1)。先进行一趟快速排序，选取第一个关键码a₁为标准。这趟排序后，数组a[]分为两个区：从a[l]到a[i-1]和从a[i+1]到a[r]。a[i]为原来关键码a₁的最终位置。前一区(从a[l]到a[i-1]，共i-1个元素)存放的是小于关键码a₁的元素，后一区(从a[i+1]a[r])存放的是大于关键码a₁的元素。
   此时，若k小于i-l+1，则从a[l]到a[r]的第k个最小值在前一区，为从a[l]到a[i-1]的第k个最小值，递归调用本算法即可；若k等于i-l+1，从a[l]到a[r]的第k个最小值恰为a[i]返回a[i]即可；若k大于i-l+1，则从a[l]到a[r]的第k个最小值在后一区，为从a[i+1]到a[r]的第k-i+l-1个最小值，递归调用本算法即可。
   (2)算法
   typedef int KeyType;
   int find(KeyType*a,int 1,int r,int k){  /*在数组a[]中从a[l]到a[r]的部分找出第k个最小值*/
       int i,j;
       KeyType temp;
       i=1:
       j=r;
       temp=a[i];
       while(i!=j){    /*一趟快速排序,寻找a[l]到最终位置*/
         while((a[j]＞=temp)&&(j＞i))
           j--;    /*j从右向左扫描*/
         if(i＜j)
           a[i++]=a[j];
           while((a[i]＜=temp)&&(j＞i))
               j++;    /*i从左向右扫描*/
           if(i＜j)
               a[j--]=a[i];
       }
       a[i]=temp;
       if(k=i-1+1)
           return a[i];    /*从a[l]到a[r]的第k个最小值恰为a[i]*/
       else{
           if(k＞i-1+1)
             return find(a,i+1,r,k-i+1-1);
             /*从a[1]到a[r]的第k个最小值为从a[i+1]到a[r]的第k-i+1-1个最小值*/
           else
             return find(a,l,i-1,k);
             /*从a[l]到a[r]的第k个最小值为从a[l]到a[i-1]的第k个最小值*/
       }
   }
   (3)代价分析
   在整个数组a[]中找出第k个最小值，只需调用find(a，0，n-1，k)即可。
   在最佳情况下，每次划分使两个区的长度大概相等。设C(n)为对长度为n的数组a[]调用find(a，0，n-1，k)所需的比较次数。则
   C(n)≤n+C(n/2)≤n+n/2+C(n/4)≤n+n/2+n/4+C(n/8)≤…
   ≤n+n/2+n/4+…+2+C(1)≤2n+C(1)=O(n)
   上式中C(1)为一常数。而移动次数不大于比较次数，所以最佳时间复杂度为O(n)。
   类似于快速排序，该算法的平均时间复杂度等于其最佳时间复杂度，为O(n)。