分治算法(2)_快速排序_排序数组
个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创分治算法(2)_快速排序_排序数组
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 快速排序简介:
原理:
时空复杂度分析:
优缺点:
2. 题目链接:
3. 题目描述:
4. 解法(快速排序)
快速排序算法思路:
快速排序的缺点;
1. 数组有序或重复效率低
2. 对于较小规模的数据，快速排序可能不如插入排序高效
快速排序的优化:
1. 随机取key
2. 数组分三块
代码展示:
结果分析:
温馨提示:
这里并不会对快速排序进行详细讲解,只会对它的思想进行解释,如果大家想看详细讲解版的,可以去下面博客查看:
排序算法(4)之快速排序(1)-CSDN博客
1. 快速排序简介:
原理:
选择基准：从待排序的数组中选择一个元素作为“基准”（Pivot），通常可以选择第一个元素、最后一个元素或随机选择。
分区：将数组中的其他元素根据基准值进行分区。所有小于基准值的元素移动到基准值的左侧，所有大于基准值的元素移动到右侧。这样，基准值的最终位置就确定了。
递归排序：对基准值左侧和右侧的两个子数组递归进行快速排序。
合并结果：由于子数组已经排序完毕，因此只需要将它们与基准值组合在一起即可。
时空复杂度分析:
时间复杂度
平均时间复杂度：O(n log n)
最坏时间复杂度：O(n²)，通常发生在选择的基准值极端不平衡时（例如，已经排好序的数组）。
最佳时间复杂度：O(n log n)
空间复杂度
快速排序的空间复杂度为O(log n)，因为递归调用的深度为O(log n)。它是一种原地排序算法，不需要额外的存储空间。
优缺点:
优点：
平均情况下性能优异。
原地排序，节省空间。
可以选择不同的基准选择策略以优化性能。
缺点：最坏情况下的时间复杂度较高。
对于较小规模的数据，快速排序可能不如插入排序高效。
2. 题目链接:
OJ链接 : 排序数组
3. 题目描述:
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
4. 解法(快速排序)
快速排序算法思路:
1. 选择基准值： 通常选择数组的第一个元素作为基准值，也可以随机选择数组中的某个元素。
2. 划分过程： 使用两个指针，一个从左边开始（左指针），一个从右边开始（右指针）。它们分别向中间移动，直到找到需要交换的元素。
3. 具体步骤：
i. 左指针移动： 从左往右找到第一个大于或等于基准值的元素。
ii. 右指针移动： 从右往左找到第一个小于或等于基准值的元素。
iii. 交换元素： 如果左指针所指元素大于基准值，并且右指针所指元素小于基准值，则交换这两个元素。
iv. 继续移动指针： 继续移动左右指针，直到它们相遇。
4. 交换基准值： 最后将基准值与右指针所指的元素进行交换，使得基准值左侧的元素都小于或等于基准值，右侧的元素都大于或等于基准值。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if (right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
}
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div + 1, right);class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
qsort(nums, 0, nums.size() - 1);
return nums;
}
void qsort(vector<int>& arr, int left, int right)
{
if(left >= right) return;
int key = left;
int begin = left;
int end = right;
while(begin < end)
{
while(begin < end && arr[end] >= arr[key]) end--;
while(begin < end && arr[begin] <= arr[key]) begin++;
swap(arr[begin], arr[end]);
}
swap(arr[key], arr[begin]);
key = begin;
//[left, key - 1][key][key + 1, right]
qsort(arr, left, key - 1), qsort(arr, key + 1, right);
}
}; 
快速排序的缺点;
1. 数组有序或重复效率低
当数组有序时,如果key还是取数组中第一个值得话,快排得递归深度就退化为O(N),整体的时间复杂度就退化为O(N^2)
2. 对于较小规模的数据，快速排序可能不如插入排序高效
对于较小的数据集，快速排序的递归深度可能较高，每次递归调用都会消耗额外的栈空间，这在小规模数据上显得不够高效。
快速排序的优化:
1. 随机取key
因为key取数组第一个数或者最后都会在数组有序中效率退化,所以我们可以直接取随机值,这样我们的递归深度是接近O(logN)--详细证明大家可以去看算法导论
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
qsort(nums, 0, nums.size() - 1);
return nums;
}
void qsort(vector<int>& arr, int left, int right)
{
if(left >= right) return;
int key = left;
int begin = left;
int end = right;
while(begin < end)
{
while(begin < end && arr[end] >= arr[key]) end--;
while(begin < end && arr[begin] <= arr[key]) begin++;
swap(arr[begin], arr[end]);
}
swap(arr[key], arr[begin]);
key = begin;
//[left, key - 1][key][key + 1, right]
qsort(arr, left, key - 1), qsort(arr, key + 1, right);
}
};
可以看到这一次通过了19个例子,卡在一个超长的连续数组, 因为这样无论怎么随机,取到的数都相同,递归深度退化为O(N),需要我们使用数组分成三块来解决!
2. 数组分三块
我们直接将数组分成三块 : 小于key, 等于key, 大于key.这样我们再遇到上次的超长重复数组,我们可以直接以O(1)的时间复杂度解决它
算法思路:
1. 定义递归出口
2. 利用随机选择基准函数生成一个基准元素
3. 将数组分成三个区域
4. 递归处理左边区域和右边区域
代码展示:
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(NULL));
qsort(nums, 0, nums.size() - 1);
return nums;
}
void qsort(vector<int>& nums, int l, int r)
{
if(l >= r) return;
int key = getRandom(nums,l,r);
int i = l, left = l - 1, right = r + 1;
while(i < right)
{
if(nums[i] < key) swap(nums[++left], nums[i++]);
else if(nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
qsort(nums, l, left), qsort(nums, right, r);
}
int getRandom(vector<int>& nums, int left, int right)
{
int r = rand();
return nums[left + r % (right - left + 1)];
}
};
结果分析:
经过改良后的快排能过顺利通过!!!并且效率还很不错!!!
最重要的的是代码只有不到30行,大家可以作为模板
这里不得不吐槽一下官方提供的快速排序解法通过不了的问题,总之这个快排算法很优秀!