学步园

 分治法求第k小元素
2010/05/15 下午 07:14
描述

用分治法求第k小元素
输入：程序从标准输入读入数据，第一行是一个整数n (1=<n<=100000)表示元素的个数，接下来的n行中每行有一个整数。最后一行是k，就是我们要找的第k小元素。

输出：针对每一组输入，输出一个结果，每个结果占一行。

解题思路：

对此题有很多种做法，最简单的一种做法可能就是直接调用C++中的sort函数排序，可是这明显不是分治法，违背了题目的本意，不过容易想到，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int a[100002];
int main()
{
    int n, k;
    int i;
    cin >> n;
    for(i = 0; i < n; i ++)
        cin >> a[i];
    cin >> k;
    sort(a, a + n);
    cout << a[k-1] << '\n';
    return 0;
}

如果真正按照题目的要求来做，那就要按照先分类，再排序，再选择的方法来做，那个比较麻烦，在这里不说了，见代码：

#include<stdio.h>
int a[100000]={0};

void Swap(int x,int y)
{
     int temp=a[x];
     a[x]=a[y];
     a[y]=temp;
}

void Bubble(int p,int r)
{
     int i,j,t;
     for(i=p;i<=r;i++)
     {
         t=i;
         for(j=i+1;j<=r;j++)
             if(a[j]<a[t]) t=j;
         if(t!=i) Swap(i,t);
         }
}

int Partition(int p,int r,int x)
{
    int i=p-1,j=r+1,t;
    for(t=0;;t++)
    {
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break;
        Swap(i,j);
        }
    return j;
}

int Select(int p,int r,int k)
{
    int i,s,t,x,j;
    if(r-p<75)
    {
        Bubble(p,r);
        return a[p+k-1];
        }
    for(i=0;i<=(r-p-4)/5;i++)
    {
        s=p+5*i;
        t=s+4;
        Bubble(s,t);
        Swap(p+i,s+2);
        }
    x=Select(p,p+(r-p-4)/5,(r-p+6)/10);
    i=Partition(p,r,x);
    j=i-p+1;
    if(k<=j) return Select(p,i,k);
    else return Select(i+1,r,k-j);
}
                             
int main()
{
    int n,k,i,x;
    scanf("%d",&n);
    for(i=0;i<n;i++)
scanf("%d",&a[i]);
    scanf("%d",&k);
    x=Select(0,n-1,k);
    printf("%d\n",x);
    return 0;
}