快速排序常用模板
- 这里的下标范围是[left,right]
代码模板：
void Quick_Sort(vector<int> &nums, int left, int right)
{
if (left < right) {
int i = left, j = right;
// 中轴值随机获取
swap(nums[rand()%(right - left + 1) + left], nums[left]);
int temp = nums[left];
while (i < j) {
while (i < j && nums[j] >= temp) {
--j;
}
swap(nums[i], nums[j]);
while (i < j && nums[i] <= temp) {
++i;
}
swap(nums[i], nums[j]);
}
// 此时的i=j,所以不用纠结是i-1还是j-1
Quick_Sort(nums, left, i - 1);
Quick_Sort(nums, i + 1, right);
}
}
- 但是当数组区间较小时，如果继续使用快排的话会导致效率降低。此时的数组已经基本有序，改用插入排序会提高排序的效率。
优化1：快排+插入
代码模板：
void Quick_Sort(vector<int> &nums, int left, int right)
{
if (left < right) {
// 当区间较小时，改用插入排序，此处不进行实现
if (right - left < 15) {
Insert_Sort(nums, left, right);
return ;
}
int i = left, j = right;
// 中轴值随机获取
swap(nums[rand()%(right - left + 1) + left], nums[left]);
int temp = nums[left];
while (i < j) {
while (i < j && nums[j] >= temp) {
--j;
}
swap(nums[i], nums[j]);
while (i < j && nums[i] <= temp) {
++i;
}
swap(nums[i], nums[j]);
}
Quick_Sort(nums, left, i - 1);
Quick_Sort(nums, i + 1, right);
}
}
优化2：三路快排
思路：
-
核心思想：将数组分为三部分
- 小于中轴值部分 [left,l-1]
- 等于中轴值部分 [l,r]
- 大于中轴值部分 [r+1,right]
-
i指针从左往右遍历
- 如果nums[i]小于temp的值，就交换nums[l]和nums[i]，i和l同时向右移动 ；
- 如果nums[i]等于temp的值，i往右移动；
- 如果nums[i]大于temp的值，就交换nums[r]和nums[i]，r向左移动，i不动
- 因为i跟r交换后，还需要再比较交换后的数，所以i不能动
-
遍历结束时
- l在第一个等于中轴值位置上
- r在最后一个等于中轴值位置上
- i在一个等于中轴值位置的后一个，即i = r + 1
代码模板：
// 三路快排
void Quick_Sort(vector<int> &nums, int left, int right)
{
if (left < right) {
// 当区间较小时，改用插入排序，此处不进行实现
if (right - left < 15) {
Insert_Sort(nums, left, right);
return;
}
int l = left;
int r = right;
int i = left + 1; // i = left也可以，不过会多一次无意义的比较
// 随机中轴值
swap(nums[left], nums[rand() % (right - left + 1) + left]);
int temp = nums[left];
while (i <= r) {
if (nums[i] < temp) {
swap(nums[i++], nums[l++]);
}
else if (nums[i] == temp) {
i++;
}
// 换完以后的nums[i]不一定比temp小，所以i不能移动
else if (nums[i] > temp) {
swap(nums[i], nums[r--]);
}
}
// 循环结束后，[l,r]区间内的数都为temp，i在r+1的位置
// [left,l-1]
Quick_Sort(nums, left, l - 1);
// [r+1,right]
Quick_Sort(nums, r + 1, right);
}
}
提供代码测试三路快排
#include <bits/stdc++.h>
using namespace std;
class Print
{
public:
void operator()(int val)
{
cout << val << " ";
}
};
// 插入排序
void Insert_Sort(vector<int> &nums, int left, int right)
{
// 注意下标从left开始
for (int i = left; i <= right; i++) {
int temp = nums[i];
int j;
// j用来找比nums[i]小的数，也就是j+1是nums[i]的位置
// 如果nums[j]比nums[i]大的话，就移到后面去
// 注意：循环里的判断要用temp不能用nums[i],nums[i]在循环里可能会改变
for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
}
// 三路快排
void Quick_Sort(vector<int> &nums, int left, int right)
{
if (left < right) {
// 当区间较小时，改用插入排序，此处不进行实现
if (right - left < 15) {
Insert_Sort(nums, left, right);
return;
}
int l = left;
int r = right;
int i = left + 1; // i = left也可以，不过会多一次无意义的比较
// 随机中轴值
swap(nums[left], nums[rand() % (right - left + 1) + left]);
int temp = nums[left];
// cout <<"temp: " << temp << " | " << endl;
// for_each(nums.begin(), nums.end(), Print());
// puts("");
while (i <= r)
{
if (nums[i] < temp) {
swap(nums[i++], nums[l++]);
// cout << nums[i] << " < " << temp << " 跟l交换之后，l和i同时移动" << endl;
}
else if (nums[i] == temp) {
i++;
// cout << nums[i] << " = " << temp << " i移动" << endl;
}
// 换完以后的nums[i]不一定比temp小，所以i不能移动
else if (nums[i] > temp) {
swap(nums[i], nums[r--]);
// cout << nums[i] << " > " << temp << " 跟r交换之后，r向左移动" << endl;
}
// for_each(nums.begin(), nums.end(), Print());
// puts("");
}
// puts("\n");
// 循环结束后，[l,r]区间内的数都为temp，i在r+1的位置
// [left,l-1]
Quick_Sort(nums, left, l - 1);
// [r+1,right]
Quick_Sort(nums, r + 1, right);
}
}
int main()
{
vector<int> nums = {3, 1, 6, 4, 5, 3, 3, 1, 7, 11, 5, 7, 3, 1, 1, 2, 7, 5, 9, 10, 8};
Quick_Sort(nums, 0, nums.size() - 1);
for_each(nums.begin(), nums.end(), Print());
}
