912. 排序数组
难度中等506收藏分享切换为英文接收动态反馈
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
题目思路：
用来当快速排序模板
寻找数组中的中间值用来快速排序，软件将中间值与数组最右边的值进行互换，
之后遍历数组，小于flag的，与num[i]互换，
将小于flag的往左边放，大于的往右边放
，软件再分割成两部，递归重复上述操作-本题的意义用来当快速排序的代码模板
Python代码：
class Solution: def dfs1(self , nums , l , r): miding = random.randint(l , r) #构建哨兵 nums[miding] , nums[r] = nums[r] , nums[miding] #将哨兵放入最右边 i = l-1 #i用来指向大于哨兵的值 for j in range(l , r): if nums[j] <nums[r]: i += 1 nums[i] , nums[j] = nums[j] , nums[i] i += 1 nums[i] , nums[r] = nums[r] , nums[i] #将哨兵放入大于哨兵的值和小于哨兵的值之间 return i def dfs_quick(self , nums , l , r): if r-l<=0: #结束标注 return mid = self.dfs1(nums, l , r) self.dfs_quick(nums , l , mid-1) self.dfs_quick(nums , mid+1 , r) def sortArray(self, nums: List[int]) -> List[int]: self.dfs_quick(nums, 0, len(nums) - 1) return nums
C++代码：
class Solution { int dfs(vector<int> &nums , int l , int r){ int miding = rand() % (r - l + 1) + l;//rand() % (b-a+1)+ a ; 就表示 a~b 之间的一个随机整数。找哨兵 swap(nums[r] , nums[miding]);//交换两个的值 int i = l-1; for (int j=l; j<=r-1; j++){ if (nums[j] < nums[r]){ //将比中间值小的值都放到左边，比中间值大的都放到右边 i用来指向大于哨兵的值 i += 1; swap(nums[i] , nums[j]); } } swap(nums[i+1] , nums[r]); //将哨兵放入小的值和大的值之间 return i+1; } void dfs_quick(vector<int> &nums , int l , int r){ if (r-l<=0){ return; } int mid = dfs(nums , l , r); //将数组分为整理好的小于哨兵的值 和 大于哨兵的值，然后分别继续细分进行排序 dfs_quick(nums , l , mid-1); dfs_quick(nums , mid+1 , r); } public: vector<int> sortArray(vector<int>& nums) { srand((unsigned)time(NULL)); //建立随机数 dfs_quick(nums , 0 , (int)nums.size()-1); return nums; } };
