問題（荷蘭國旗問題）：
給定一個數組arr，和一個數num，請把小于num的數放在數組的左邊，等于num的數放在數組的中間，大于num的數放在數組的右邊。
要求額外空間複雜度O(1)，時間複雜度O(N)
Coding：
當arr[cur]<num的時候：
将less+1與cur的值進行交換，然後cur+1；
最終指針位置結果：less=less+1，cur=cur+1；
當arr[cur]>num的時候：
将more-1與cur的值進行交換
最終指針位置：more=more-1
當值相等的情況下：
隻需要将cur向右移動一位就可以了。
傳回的是等于區域的左邊界和右邊界：
源碼：
package cn.mxl;
public class NetherlandFlag {
public static void main(String[] args) {
int[] arr= {4,6,8,4,2,8,5,9,8,6,5,4,5,5,5};
partition(arr, 0, arr.length-1,5);
for (int i : arr) {
System.out.println(i);
}
}
public static int[] partition(int[] arr, int L,int R,int num) {
int less=L-1;
int more=R+1;
int cur=L;
while(cur<more) {
if(arr[cur]<num) {
swap(arr,++less,cur++);
}else if(arr[cur]>num) {
swap(arr,--more,cur);
}else {
cur++;
}
}
return new int[] {less+1,more-1};
}
private static void swap(int[] arr, int i, int j) {
// TODO Auto-generated method stub
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
荷蘭國旗問題在經典快排的應用Coding:
public class QuickSort {
public static void main(String[] args){
int[] arr= {3,1,8,7,9,5};
myQuickSort(arr,0,arr.length-1);
for (int i = 0; i <arr.length ; i++) {
System.out.println(arr[i]);
}
}
public static void myQuickSort(int[] arr,int l,int r){
if (l<r){
int[] pos=partition(arr,l,r);
myQuickSort(arr,l,pos[0]-1);
myQuickSort(arr,pos[1]+1,r);
}
}
private static int[] partition(int[] arr, int l, int r) {
int less=l-1;
int more=r;
int cur=l;
while (cur<more){
if (arr[cur]<arr[r]){
mySwap(arr,++less,cur++);
}else if (arr[cur]>arr[r]){
mySwap(arr,--more,cur);
}else {
cur++;
}
}
mySwap (arr,cur,r);
return new int[]{less+1,more+1}; //cur==more，而cur（more）與r交換之後位置上是r
}
private static void mySwap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
簡單了解：
經典的快排是取一個值然後隻分了兩種情況，左邊放小于的數，右邊放大于等于的數，根據荷蘭國旗問題，我們改進，在中間直接添加了一個等于區域。不過其實時間複雜度是一樣的。
問題來說，由于經典快排，要根據所取的值來決定，如果全部取到最中間那它的時間複雜度為O(N*logN)，如果全部取值到最左或者最右，那麼它的時間複雜度為O(N^2)。
是以我們可以随機的添加一個開始的最右值來實作更加随機的取值
随機快排算法
代碼和以前一樣，隻是多了一個之前注釋的行。
總結：随機快排是最常用的一種排序方式，重點！
時間複雜度：O(N*logN)
額外空間複雜度：O(logN)：記錄斷點的位置所消耗的空間。