題目鏈接
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;}
}