[关闭]
@yexiaoqi 2022-06-09T17:06:07.000000Z 字数 893 阅读 414

912. 排序数组

刷题 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


题目中数组长度范围比较大,考虑使用快速排序,因为它快呀

  1. class Solution {
  2. //数组长度范围比较大,考虑使用快速排序
  3. public int[] sortArray(int[] nums) {
  4. quickSort(nums, 0, nums.length-1);
  5. return nums;
  6. }
  7. Random random = new Random();
  8. //对数组nums的区间[left,right]的元素进行排序
  9. private void quickSort(int[] nums, int left, int right){
  10. if(left>=right) return;
  11. int index = left+random.nextInt(right-left+1);//随机化,避免极端情况效率低下
  12. int pivot=nums[index]; //先把基准元素提出来
  13. nums[index]=nums[left]; //最左边产生一个坑位
  14. int L=left, R=right;
  15. while(L<R){
  16. while(L<R && nums[R]>=pivot) R--; //找到右边第一个小于基准的元素
  17. nums[L]=nums[R]; //将此元素填入左边的坑中(基准左侧)
  18. while(L<R && nums[L]<=pivot) L++; //找到右边第一个大于基准的元素
  19. nums[R]=nums[L]; //将此元素填入右边的坑中(基准右侧)
  20. }
  21. nums[L]=pivot; //左右指针重合后,将基准元素放回重合位置
  22. //基于分治思想对左右区间排序
  23. quickSort(nums,left,L-1);
  24. quickSort(nums,L+1,right);
  25. }
  26. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注