线性时间选择问题——分治

问题：
求一个n个数的列表中第K个最小的元素。这个数字被称为第K个顺序统计量。

问题求解：

// 对数组元素data[lowhigh]进行分区操作,0号单元不用
int  partion( int  data[], int  low, int  high)
{
    data[ 0 ] = data[low];
     int  pivotkey = data[low];
     while (low < high)
    {
         while (low < high && data[high] >= pivotkey)
             -- high;
        data[low] = data[high];
         while (low < high && data[low] <= pivotkey)
             ++ low;
        data[high] = data[low];
    }
    data[low] = data[ 0 ];
     return  low;
}
/* 查找data[pr]中第k大的数.
**平均情况下，它比快速排序应该要快，因为分区之后只用处理一个子数组，而
**而快速排序要处理两个独立的子数组。
**T(n)=T(n/2)+(n+1)
**T(n)=O(n)
*/
int  lineselect( int  data[], int  p, int  r, int  k)
{
     // p不能大于r
     if (p > r)
         return   - 1 ; 
      if (p == r)
            return  data[p];
     // p<r
     int  s = partion(data,p,r);
     if  (s == k)
         return  data[s];
     else   if (s > k)
    {
         int  r1 =  lineselect(data,p,s - 1 ,k);
         return  r1;
    }
     else    // s<k
    {
         int  r1 = lineselect(data,s + 1 ,r,k);
         return  r1;
    }
}
/* 快速排序：
**T(n)=2T(n/2)+n
**T(n)=nlogn
*/
void  QSort( int   * v, int  low, int  high)
{
     int  pivotloc = 0 ;
     if (low < high)
    {
        pivotloc = Partition(L,low,high);
        QSort(v,low,pivotloc - 1 );
        QSort(v,pivotloc + 1 ,high);
    }
}