查找第k小的元素-减治法

问题描述:n个数中找出第k小的元素

输入:

9
5 3 8 1 4 6 9 2 7
4

输出:

4

用快排思想先找出数组中第一个元素的位置(博客中有快排算法):

                     排序前:5 3 8 1 4 6 9 2 7

                     排序后:2 3 4 1 5 6 9 8 7    (5的位置确定了)

用k与元素5的下标计较,等于就输出,小于递归5前的元素,大于递归5后的元素

代码:

#include<iostream>

using namespace std;

void QuickSort(int *a,int left,int right,int k)
{
    int i=left;
    int j=right;

    while(i<j)
    {
        int temp;
        //从后往前比较
        while(i<j && a[i]<a[j])
            j--;
        if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;
        }
        //从前往后比较
        while(i<j && a[i]<a[j])
            i++;
        if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            j--;
        }
    }
    
    if(k==i)
    {
        cout<<a[k];
        return;
    }
    else if(k<i)
    {
        QuickSort(a,left,i-1,k);
    }
    else
    {
        QuickSort(a,j+1,right,k);
    }
}
int main()
{
    int n;
    int k;
    int a[100];
    cin>>n;
    int left=1,right=n;//对应下标位置
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    cin>>k;
    QuickSort(a,left,right,k);
    return 0;
}
上一篇:分页技巧_改进JSP页面中的公共分页代码_实现分页时可以有自定义的过滤与排序条件


下一篇:排序-快速排序