快排找出第K大的数（C++实现）-蒲公英云

快排找出第K大的数（C++实现）

蔚落 2024-03-16 14:46 162阅读 0赞

算法实现：

#include <stdio.h>
void printAll(int a[], int n){
    int i;
    for(i=0; i<n; i++){
        printf("%d ", a[i]);
    }
}
void quick_find_K(int a[], int low, int high, int kn){
    int base = a[low];
    int i=low, j=high, k=low;
    // 终止条件：i和j碰面，即i=j
    while(i < j){
        // 当i不为坑的下标
        while(i!=k){
            // 且i对应元素小于或等于基准元素，右移
            if(a[i] <= base){
                i++;
            // 当i对应元素大于基准元素，则与坑进行交换
            }else{
                a[k] = a[i];
                k = i;
        }
    }
        // 当j不为坑的下标
        while(j!=k){
            // 且j对应元素大于或等于基准元素，左移
            if(a[j] > base){
                j--;
            // 当j对应元素小于基准元素，则与坑进行交换
            }else{
                a[k] = a[j];
                k = j;
            }
        }
    }
    // 基准元素放到i和j的相遇位置，完成基准元素的位置定位
    a[i] = base;
    // 如果i与要求第k大的元素位置相等，则打印其值并结束
    if(i == kn){ 
        printf("%d", a[i]);
    // 如果i小于第k大的元素位置，由于快排的特性，第k大元素位置一定在右边
    }else if(i < kn){
        quick_find_K(a, i+1, high, kn);
    // 如果大于第k大的元素位置，由于快排的特性，第k大元素位置一定在左边
    }else{
        quick_find_K(a, low, i-1, kn);
    }
}
int main(){
    int a[9] = {27, 84, 21, 47, 15, 25, 68, 35, 24};
    int k = 3;
    quick_find_K(a, 0, 8, 9-k);
    printf("\n");
    return 0;
}