编辑代码

#include <iostream>

void quick_sort_kth(int q[], int l, int r, int k)
{
    //递归的终止情况
    if (l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) std::swap(q[i], q[j]);
    }

    // 判断第 k 大的元素在哪个区间
    if (k <= j) {
        quick_sort_kth(q, l, j, k);
    } else {
        quick_sort_kth(q, j + 1, r, k);
    }
}

int main() {
    int arr[] = {12, 7, 11, 5, 6, 13, 6};
    int n = sizeof(arr) / sizeof(int);
    int k = 3; // 找第 3 大的数

    std::cout << "Original array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }

    quick_sort_kth(arr, 0, n - 1, n - k);

    std::cout << "\nSorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }

    std::cout << "\nThe " << k << "th largest element is: " << arr[n - k] << std::endl;

    return 0;
}