题目链接
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;}
}
)
