【数组分三段快排】分而治之的快排算法

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