题目链接

912. 排序数组 - 力扣（LeetCode）

题目解析

算法原理

使用数组分三块的思想

i用来遍历整个数组

left用来标记<key的边界

right用来标记>key的边界

然后i进行遍历,数组就分成了四块

[l,left]<key

[left+1,i-1]==key

[i,right-1]未知

[right,r]>key

最后划分完后就是[l,left]<key,[left+1,right-1]=key,[right,r]>key

分类讨论

代码编写

class Solution {//交换void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}void quickSort(int[] nums, int l, int r) {if (r <= l) {//递归出口return;}int left = l - 1;int right = r + 1;int key = nums[(right + left) / 2];int i = l;while (i < right) {// 此时数组分成四块[l,left]<key,[left+1,i]==key,[i+1,right-1]未知,[right,r]>keyif (nums[i] < key) {// 去左边swap(nums, i++, ++left);} else if (nums[i] == key) {i++;} else {// 去右边swap(nums, i, --right);}}// 处理左边quickSort(nums, l, left);// 处理右边quickSort(nums, right, r);}public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}
}

注意

1> 必须有出口: l>=r

2> 去右边不让i++的原因是,right-1的位置是未知的,所有交换完后i下标的数是未知的,还没有进行判断

二刷

class Solution {void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}void quickSort(int[] nums, int l, int r) {// 处理递归出口if (l >= r) {return;}// left,right标记边界int left = l - 1;int right = r + 1;// 中间值int key = nums[(right + left) / 2];// 遍历int i = l;// 数组分成四块[l,left]<key,[left+1,i-1]==key,[i,right-1]未知,[right,r]>keywhile (i < right) {if (nums[i] < key) {// 去左边swap(nums, i++, ++left);} else if (nums[i] == key) {// 直接往后走i++;} else {// 去右边swap(nums, i, --right);}}// 处理key的左边quickSort(nums, l, left);// 处理key的右边quickSort(nums, right, r);}public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}
}