目录
- 1.前言
- 2.题目简介
- 3.求解思路
- 4.示例代码
1.前言
算法中的快排
2.题目简介
题目链接:LINK
3.求解思路
这个题很简单写一个快排就行。
数组分三段(分而治之):但是相对于我们之前写的霍尔版、挖坑法、交换法快排,这个题目可能有很多重复的数字,这些重复的数字无疑会大大提高栈帧消耗,很有可能导致崩溃。于是我们使用数组分三段的方法来做。
随机选key:之后为了进一步去优化,我们key值(中间参照值)可以随机取,不仅仅限于三数取中,在某些情况下比三数取中选key略好一点点。
4.示例代码
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(nullptr));//种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int begin, int end){if(begin >= end) return;//1.选择基准值int key = getRandom(nums, begin, end);//2.数组分三块int left = begin - 1, right = end + 1;int i = begin;while(i < right){if(nums[i] < key){swap(nums[i++], nums[++left]);}else if(nums[i] == key){i++;}else //nums[i] > key{swap(nums[i], nums[--right]);}}//3.对其左右区域依次再次划分三块qsort(nums, begin, left);qsort(nums, right, end);} int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left + 1) + left];}
};
EOF