C++快速排序及优化（三路快排）

快速排序常用模板

• 这里的下标范围是[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-1Quick_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);}
}

• 但是如果数组区间内相等元素较多，算法最后可能退化为O(n^2)的算法，所以就有了优化三路快排

优化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 
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());
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！