computer 版 (精华区)

发信人: remember (Learning C++), 信区: program
标  题: Re: 找第n个最小数
发信站: 听涛站 (2001年10月16日20:40:11 星期二), 站内信件

  首先，我们的思想还是划分（分治）：
  (1)把n个输入元素划分为[n/5]个组，每组5个元素，除可能一组不是5个。
     用任意排序算法，将每组元素排序，并取出中位数。
  (2)递归调用select来找这[n/5]个元素的中位数，如果[n/5]是偶数，那么
     找两个中位数中较大的一个。然后以此元素为划分基准。

  int select(int a[], int p, int r, int k)
  {
    if (r-p<75) { 用简单排序对a[p:r]排序，return a[p+k-1]; }
    for ( int i=0; i<=(r-p-4)/5; i++)
       将a[p+5*i]至a[p+5*i-4]的第三小元素与a[p+i]交换位置
    int x = select(a,p,p+(r-p-4)/5,(r-p-4)/10);
    i = Partition(a,p,r,x); //以a[p]为基准元素把a[p:r]分为两半
                            //具体参考Quicksort
    j = i-p+1;
    if (k<=j) return select(a,p,i,k);
    else return select(a,i+1,r,k-j);
  }

--
    洛阳亲友如相问  一片冰心在玉壶
※ 来源:·听涛站 tingtao.dhs.org·[FROM: 匿名天使的家]