@yexiaoqi
2022-06-09T17:06:07.000000Z
字数 893
阅读 414
刷题
leetcode
题目:给你一个整数数组 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]
提示:
链接:https://leetcode.cn/problems/sort-an-array
题目中数组长度范围比较大,考虑使用快速排序,因为它快呀
class Solution {
//数组长度范围比较大,考虑使用快速排序
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length-1);
return nums;
}
Random random = new Random();
//对数组nums的区间[left,right]的元素进行排序
private void quickSort(int[] nums, int left, int right){
if(left>=right) return;
int index = left+random.nextInt(right-left+1);//随机化,避免极端情况效率低下
int pivot=nums[index]; //先把基准元素提出来
nums[index]=nums[left]; //最左边产生一个坑位
int L=left, R=right;
while(L<R){
while(L<R && nums[R]>=pivot) R--; //找到右边第一个小于基准的元素
nums[L]=nums[R]; //将此元素填入左边的坑中(基准左侧)
while(L<R && nums[L]<=pivot) L++; //找到右边第一个大于基准的元素
nums[R]=nums[L]; //将此元素填入右边的坑中(基准右侧)
}
nums[L]=pivot; //左右指针重合后,将基准元素放回重合位置
//基于分治思想对左右区间排序
quickSort(nums,left,L-1);
quickSort(nums,L+1,right);
}
}