快速排序回顾及相关题型

快速排序

基本思想

快排的本质其实是分治算法

分：先选定一个数作为基准点x，将所有小于x的数放到x的左边，将所有大于x的数放到x的右边。将所有的数按照此法分成左右两个区间。

治：递归调用左右两个区间，对左右两个区间进行快速排序。

合并：对于快速排序，合并操作无需单独进行。

程序代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int n;
int a[N];

void qsort(int l, int r)
{
    if(l >= r)  return ;
    // 子问题划分
    // 最终得到的子问题划分点是j
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while(i < j) {
        while(a[++i] < x) ;
        while(a[--j] > x) ;
        if(i < j) {
            swap(a[i], a[j]);
        }
    }
    // 递归处理子问题
    qsort(l, j);
    qsort(j + 1, r);
    // 子问题合并：这一步快排不需要操作
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    qsort(0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

时间复杂度

时间复杂度为 $O(NlogN)$

最小K个数

题目描述

原题链接

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

问题分析

分：找一个基准元素x，将数组中比x小的元素放在x的左边，比x大的元素放在y的右边，并得到基准元素x的划分位置j。

治：

• 若j <= k：说明前 k 小的数分布在左右区间，因此需要对左右区间分别进行递归调用快速排序。【由于元素下标从 0 开始，因此第k小对应下标应该是k - 1】
• 若j > k：说明前 k 小的数只分布在左区间，因此只需要对左区间进行递归调用快速排序。

合并：合并操作无需单独进行。

程序代码

class Solution {
private:
    void qsort(vector<int>& arr, int l, int r, int k) {
        if(l >= r)  return;
        int i = l - 1, j = r + 1, x = arr[l + r >> 1];
        while(i < j) {
            while(arr[++i] < x) ;
            while(arr[--j] > x) ;
            if(i < j)  swap(arr[i], arr[j]);
        }
        qsort(arr, l, j, k);
        if(k >= j)  qsort(arr, j + 1, r, k);
    }

public:
    vector<int> smallestK(vector<int>& arr, int k) {
        int n = arr.size();
        qsort(arr, 0, n - 1, k);
        return vector<int>({arr.begin(), arr.begin() + k});
    }
};

时间复杂度

时间复杂度的期望为 $O(N)$，证明比较繁琐，可以参考《算法导论》

数组中的第K个最大元素

题目描述

题目描述

给定整数数组?nums?和整数?k，请返回数组中第?k?个最大的元素。

请注意，你需要找的是数组排序后的第?k?个最大的元素，而不是第?k?个不同的元素。

你必须设计并实现时间复杂度为?O(n)?的算法解决此问题。

问题分析

这里先假设数组下标从 1 开始，后续程序实现时可以通过 k - 1 来对齐下标从 0 开始的数组。

分：找一个基准元素x，将数组中比x小的元素放在x的左边，比x大的元素放在y的右边，并得到基准元素x的划分位置j。

治：

• 若k <= j：说明第 k 小的数在左区间，因此只需要对左区间进行递归调用快速排序。
• 若k > j：说明第 k 小的数在右区间，因此只需要对右区间进行递归调用快速排序。

合并：合并操作无需单独进行。

程序代码

class Solution {
private:
    int qsort(vector<int>& nums, int l, int r, int k) {
        if(l >= r)  return nums[l];
        int i = l - 1, j = r + 1, x = nums[l + r >> 1];
        while(i < j) {
            while(nums[++i] > x)  ;
            while(nums[--j] < x)  ;
            if(i < j)  swap(nums[i], nums[j]);
        }
        if(k <= j)  return qsort(nums, l, j, k);
        else  return qsort(nums, j + 1, r, k);
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return qsort(nums, 0, n - 1, k - 1);
    }
};

时间复杂度

时间复杂度的期望为 $O(N)$，证明比较繁琐，可以参考《算法导论》