快速排序回顾及相关题型

2023-12-28 11:27:21

快速排序

基本思想

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

:先选定一个数作为基准点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 ( N l o g N ) O(NlogN) 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 ) O(N) 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 ) O(N) O(N),证明比较繁琐,可以参考《算法导论》

文章来源:https://blog.csdn.net/qq_45931691/article/details/135245876
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。