利用快速排序的思想寻找第k小的元素

分治算法：我们可以取序列中任意一个元素作为媒介，并把比其小的数字放在这个元素左边，把比其大的数字放在边。
如果这个数字个数等于k，那么选取的这个元素就是案，
如果右边的数字个数大于k，则答案在右边，对右边递归
如果左边的数字个数小于k，则答案在左边，对左边递归

/*
注意⚠️这里的k的大小相对于l来说的
*/
int  kuaipai(int l,int r,int k)
{
    int i=l,j=r,key=a[i];
    while(i<j)
    {
    while(i<j&&a[j]>=key)j--;
    a[i]=a[j];
    while(i<j&&a[i]<=key)i++;
    a[j]=a[i];
    }
    a[i]=key;
    if(l<r)
    {
        if(i-l+1==k)
        {
            return key;
        }
        else if(i-l+1>k)
            return kuaipai(l,i-1,k);
        else return kuaipai(i+1,r,k-(i-l+1));
    }
     
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29