leetcode 912 排序数组(快速排序)

目录

一、题目描述

二、解题思路

整体思路

具体思路

三、代码实现

解法一：普通快速排序

解法二：三指针划分优化的快速排序算法

---

一、题目描述

二、解题思路

整体思路

可以借助三指针划分的方法来优化一般的快速排序流程，这样在重复元素较多时，可以降低时间复杂度。三指针划分的思路与leetcode75颜色分类一致。

注意：快速排序每次划分选择key值时使用随机数可以使得时间复杂度趋近O(nlogn)

具体思路

(1)采用随机数的方式产生key值，这样能够保证时间复杂度趋近于O(nlogn)，产生随机数的代码为：

int r=rand();

return nums[left+r%(right-left+1)];

rand随机产生非负整数,r%(right-left+1)的范围为[0,nums.size()-1]，可以实现在指定区间内随机生成key值；

(2)当l>=r时，表示区间内没有数字，或者只有一个数字，该区间排序完成，直接return；

(3)定义left、right、i三个指针(下标)。left用于记录小于key的区间的右端点，初始化为l-1；right用于记录大于key的区间的左端点，初始化为r+1；i用于遍历区间，初始化为l。对区间进行遍历，直至i==right：

<1>如果nums[i]==key，执行i++;

<2>如果nums[i]>key，执行swap(nums[--right],nums[i]);

<3>如果nums[i]<key，执行swap(nums[++left],nums[i++])；

三指针区间划分过程可以参考：

leetcode 75 颜色分类-CSDN博客

(4)此次划分完后，有[l,left]，[left+1,right-1]，[right][r]三个区间，再递归处理左右区间即可。

三、代码实现

解法一：普通快速排序

时间复杂度：T(n)=O(nlogn)

空间复杂度：S(n)=O(1)

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 left = l, right = r;while (left <= right) {while (nums[left] < key) left++;while (nums[right] >key) right--;if (left <= right) {swap(nums[left], nums[right]);left++;right--;}}// 现在left是左区间右边界，right是右区间左边界qsort(nums, l, right);qsort(nums, left, r);}//产生随机数int GetRandom(vector<int>& nums,int l,int r){return nums[l+rand()%(r-l+1)];}
};

解法二：三指针划分优化的快速排序算法

时间复杂度：T(n)=O(nlogn)

空间复杂度：S(n)=O(1)

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=GetRadom(nums,l,r);int left=l-1,right=r+1,i=l;while(i<right){if(nums[i]==key) i++;else if(nums[i]<key) swap(nums[++left],nums[i++]);else swap(nums[--right],nums[i]);}//[l,left],[left+1,right-1],[right,r],递归处理左右区间qsort(nums,l,left);qsort(nums,right,r);}//产生随机数int GetRadom(vector<int>& nums,int left,int right){int r=rand();return nums[left+r%(right-left+1)];}
};