算法日常・每日刷题--＜快速排序＞2
912. 排序数组 - 力扣LeetCode912. 排序数组 - 给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。 示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。 提示 * 1 nums.length 5 * 104 * -5 * 104 nums[i] 5 * 104https://leetcode.cn/problems/sort-an-array/随机基准 三路快排随机选基准随机抽取区间内数字作为 pivot从数学概率上杜绝有序数组退化平均递归深度稳定 O(logn)三路分区把区间切分成三段[l, left] key、[left1, right-1] key、[right, r] key等值元素不再参与后续递归大量重复数据下效率大幅提升原地交换仅递归栈开销无额外数组空间开销极小贴合题目「空间尽可能小」要求。三路指针含义left小于 key 区域的右边界初始l-1空区间right大于 key 区域的左边界初始r1空区间i遍历指针从头开始扫描未分区元素。分区循环逻辑nums[i] key交换到左区间lefti交换过来的数一定小于 key无需二次校验nums[i] key交换到右区间right--i 不变交换过来的数字还没判断需要重新校验nums[i] key直接跳过不做任何交换。class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); qsort(nums,0,nums.size()-1); return nums; } void qsort(vectorint nums,int l,int r) { if(lr) return; int keygetRandom(nums,l,r); int il,leftl-1,rightr1; while(iright) { if(nums[i]key) swap(nums[left],nums[i]); else if(nums[i]key) swap(nums[--right],nums[i]); else i; } //l left left1 right right1 r qsort(nums,l,left); qsort(nums,right,r); } int getRandom(vectorint n,int l,int r) { int x rand(); return n[x % (r-l1) l]; } };
