Question

一个C语言经典的分治问题

用分治方法，找出10个不同元素中第K个最小元素
这是个数据放在一个数组啊a[10]里面，a[10]={3,6,5,56,48,1,34,78,99,0}
求具体代码，运行成功再追加分数！！

Answer 1

#include <stdio.h>
int partition(int a[],int low, int high)
{
    int pivot = a[low];
    int i=low;
    int j=i+1;
    for(;j<=high;++j)
    {
        if(a[j]<pivot)
        {
            ++i;
            int temp = a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    int temp = a[i];
    a[i]=pivot;
    a[low]=temp;
    return i;
}

int findKth(int a[],int low,int high, int k)
{
    if(low==high)
        return a[low];
    int r = partition(a,low,high);
    int i=r-low+1;
    if(i==k)
        return a[r];
    else if(i<k)
        findKth(a,r+1,high,k-i);
    else
        findKth(a,low,r-1,k);
}

int main()
{

    int a[]={3,6,5,56,48,1,34,78,99,0};
    for(int i=1;i<=10;++i)
    {
        int result = findKth(a,0,9,i);
        printf("%dth->%d\n",i,result);
    }
    return 1;
}

《 算法导论》     中位数和顺序统计量     第二节有详细说明