題目

https://leetcode.com/problems/sort-colors/

題解

快速排序3.0(隨機快排+荷蘭國旗技巧優(yōu)化)

在arr[L…R]范圍上，進行快速排序的過程：

1）在這個范圍上，隨機選一個數記為num，

1）用num對該范圍做partition，< num的數在左部分，== num的數中間，>num的數在右部分。假設== num的數所在范圍是[a,b]

2）對arr[L…a-1]進行快速排序(遞歸)

3）對arr[b+1…R]進行快速排序(遞歸)

因為每一次partition都會搞定一批數的位置且不會再變動，所以排序能完成

隨機快排的時間復雜度分析

在arr[L…R]范圍上，進行快速排序的過程：

1）在這個范圍上，隨機選一個數記為num，

1）用num對該范圍做partition，< num的數在左部分，== num的數中間，>num的數在右部分。假設== num的數所在范圍是[a,b]

2）對arr[L…a-1]進行快速排序(遞歸)

3）對arr[b+1…R]進行快速排序(遞歸)

因為每一次partition都會搞定一批數的位置且不會再變動，所以排序能完成

class Solution {public void sortColors(int[] nums) {if (nums.length < 2) return;process(nums, 0, nums.length - 1);}public void process(int[] arr, int L, int R) {if (L >= R) return;swap(arr, L + (int) (Math.random() * (R - L + 1)), R); // 隨機選一個數作為基準，放在最右側int[] equalArea = netherlandsFlag(arr, L, R);process(arr, L, equalArea[0] - 1); // 小于區(qū)遞歸process(arr, equalArea[1] + 1, R); // 大于區(qū)遞歸}public int[] netherlandsFlag(int[] arr, int L, int R) {if (L > R) return new int[]{-1, -1};if (L == R) return new int[]{L, R};int less = L - 1; // 小于區(qū)的右邊界int more = R; // 大于區(qū)的左邊界int index = L; // 當前數，并且index左邊的數一定都小于等于arr[R]（pivot）while (index < more) {if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {swap(arr, index++, ++less);} else {swap(arr, index, --more);}}swap(arr, more, R);return new int[]{less + 1, more};}public void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;} }

總結

以上是生活随笔為你收集整理的leetcode 75. Sort Colors | 75. 颜色分类（荷兰国旗问题，快速排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。