LeetCode刷题笔记排序算法快速排序

编程入门行业动态更新时间:2024-10-21 12:34:58

快速排序简介

算法思想：

快速排序是对冒泡排序的一种改进，其核心算法思想是：使用基准将要排序的数据分割成小于基准和大于基准的两部分；然后在被分割的两个部分中递归按基准划分的步骤，最终递归到一个部分仅有一个元素组成，此时数组排序完成。

算法实现过程中，在使用快排之前可以将数组打乱，因为快排是不稳定的算法，在原数组大部分元素是有序的情况下效率提升不明显。

实现快排步骤如下：

先选取基准，可以以序列第一个元素作为基准然后使用碰撞指针遍历数组，从指向数组尾部的指针 tail 开始移动，将数组尾部小于基准的元素覆盖到指向数组头部的指针 head；接着移动 head 找到大于基准的元素覆盖到 tail；重复该过程直到一次遍历完成，将基准值放到指针相遇位置，将数组划分为小于基准和大于基准的两部分。在被分割的两部分中递归选择基准和划分序列的步骤，直到递归结束完成排序

执行样例：

输入：[6,1,2,7,9,3,4,5,10,8]

算法实现：

// 碰撞指针实现
void quickSort(vector<int> &nums, int l, int r) {if (l + 1 >= r) {return;}int head = l, tail = r - 1, key = nums[head];while (head < tail){while(head < tail && nums[tail] >= key) {--tail;}nums[head] = nums[tail];while (head < tail && nums[head] <= key) {++head;}nums[tail] = nums[head];}nums[head] = key;quick_sort(nums, l, head);quick_sort(nums, head + 1, r);
}// 快慢指针实现
void quickSort(vector<int> &nums, int l, int r) {if (l + 1 >= r) {return;}int cur = l;int pre = cur - 1;int key = nums[r-1];while (cur < r) {while (nums[cur] < key && ++pre != cur) {swap(nums[cur], nums[pre]);}cur++;}   swap(nums[++pre], nums[r-1]);quickSort(nums, l, pre);quickSort(nums, pre + 1, r);
}

215 数组中的第K个最大元素

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

输入一个数组和一个目标值 k，输出一个整数表示第 k 大的数字。题目默认一定有解。

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解析：

一种简单的思路就是将整个数组排完序，然后输出第 k 个最大元素。

我们可以使用快速排序的思想，减少程序的时间复杂度。根据快速排序核心思想衍生出的快速选择一般用于求解 k-th Element 问题，可以在 O(n) 时间复杂度，O(1) 空间复杂度完成求解工作。

快速选择的实现和快速排序相似，不过只需要找到第 k 大的枢（pivot）即可，不需要对其左右再进行排序，即在快速排序的基础上增加递归跳出条件，在找到第 k 大的枢时直接终止递归即可，减少时间复杂度。与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为 O(n^2)。

class Solution {
public:int partation(vector<int>& nums, int k, int start, int end){if(start>=end) return -1;// 随机化处理int idx = start + rand() % (end - start); swap(nums[start], nums[idx]);// 一遍遍历与交换int head = start, tail = end-1;int key = nums[head];while(head < tail){while(head<tail && nums[tail]>=key){--tail;}nums[head] = nums[tail];while(head<tail && nums[head]<=key){++head;}nums[tail] = nums[head];}nums[head] = key;// 计算当前枢是否为第 k 大的枢int a = end - tail;// 是第 k 大的枢直接返回if(a==k){return nums[head];}else if(a > k){// 在当前枢右侧，递归快速选择partation(nums,k,tail+1,end);}else{// 在当前枢左侧，递归快速选择partation(nums,k-a,start,tail);}return nums[nums.size()-k];}int findKthLargest(vector<int>& nums, int k) {return partation(nums,k,0,nums.size());}
};