查找第k小元素

经典算法

查找第k小元素

阅读量: 137 编辑

利用快速排序中的一个性质，即将主元素放在正确的位置，使得左边的数都比主元素小，右边的数比元素大，这样会产生一个性质：该数后面是不会移动的，即该数落在排序后的正确位置，也就是序列中第k小的数。

用 k 表示位置，如果下标是从1开始的话，那么第4小的元素就是7，也就是说一趟快速排序就确定了k的位置，后面就不需要递归了。

【输入描述】

输入两行。第一行是数组大小 n 和 k，第二是数组元素，用空格分开；

【输出描述】

输出若一行，输出数组中的第 k 小元素。

【输入样例】

8 3
7 13 4 5 8 1 11 9

【输出样例】

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

int arr[10001], k;

// 快速排序
int quickSort(int arr[], int left, int right) {
    if (left < right) {
        int base = arr[left];
        int i = left, j = right;

        while (i < j) {
            while (arr[j] > base)
                j--;
            swap(arr[i], arr[j]);

            while (arr[i] < base)
                i++;
            swap(arr[j], arr[i]);
        }

        // i = j
        arr[i] = base;
        if (k <= j - 1) {
            quickSort(arr, left, j - 1);
        }
        if (i + 1 <= k) {
            quickSort(arr, i + 1, right);
        }
    }
}

int main() {
    int n;
    cin >> n >> k;

    // 输入数组元素
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 快速排序（升序）
    quickSort(arr, 1, n);

    cout << arr[k] << endl;

    return 0;
}