快速排序求第 K 大的数或第 K 小的数

众所周知，快速排序可以通过每一趟排序将指定元素放在它应该在的位置，也就是它左边的元素都比他小，右边的元素都比他大。根据这个原理，利用快速排序求第 K 大的数或者第 K 小的数就很方便了。在实现的时候，并不需要完整地实现快排的所有过程。假如我们要找的是第 K 大的数，而一趟快排后 a[low] 这个元素被放在了指定位置，那就只需要看 K 和 low 的大小关系来决定递归 low 的左边部分还是右边部分即可。下面的代码实现的是从小到大快排求第 K 小的数，若要求第 K 大的数，可以将它看做成是第 n-k+1 小的数传参即可。或者也可以将快排的函数改成从大到小排序。

#include <cstdio>
using namespace std;

void quicksort(int a[], int start, int end, int k){
    int key, low, high;  // low 和 high 为两个指针用来不断交换 key 左右两边数的位置
    low = start;
    high = end;
    key = a[start];
    if(start < end){
        while(low < high){  //交换的过程
            while(low < high && a[high] >= key)
                high--;
            a[low] = a[high];
            while(low < high && a[low] <= key)
                low++;
            a[high] = a[low];
        }
        a[low] = key;  //每一轮交换后，low 所指的元素，即 key ，被放到了它应该在的位置
        if(low == k-1)
            printf("%dn", a[low]);
        else{
            if(low < k-1)  //根据需求选择要递归的对象，不用完整排序
                quicksort(a, low+1, end, k);
            else
                quicksort(a, start, low-1, k);
        }
    }
}

int main()
{
    int n, k;
    int a[1005];
    scanf("%d%d",&n,&k);//n 代表数组长度，k 代表求第 k 小的数，如果要求第 k 大的数，就是第 n-k+1 小的数
    for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);
    quicksort(a, 0, n-1, k);
    return 0;
}

最后

以上就是哭泣洋葱为你收集整理的快速排序求第 K 大的数或第 K 小的数的全部内容，希望文章能够帮你解决快速排序求第 K 大的数或第 K 小的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。