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

蔚落 2024-03-16 14:46 7阅读 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;
    }