问题（荷兰国旗问题）：
给定一个数组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)：记录断点的位置所消耗的空间。