（排序三）荷兰国旗与快排（三切分）
（二切分）给定一个数组arr和一个数num,小于等于这个数字的数放在数组的左边，大于这个数字的数放在数组的右边。要求：时间复杂度O（n），额外空间复杂度O(1）
思路：在此处使用一个标记，初始位置为数组最左边-1用来区分小于等于区域，在标记的左边都是小于等于区域内的数，标记的位置代表小于等于区域的最后一个数。数组从0位置开始便利，依次判断arr[i]是否小于等于num，如果是，则arr[i]与小于等于区域的前一个位置的数进行交换，刺死小于等于区域增加了一个数，less++，如果是大于，则i指针向右移（默认为两个区域，小于等于区域以外的数就是大于区域的数）。i指针到尾部停止。
（沿着数组从头到尾走一遍，默认为左边为小数右边为大数，走的过程中遇见小的数扔到小数队尾换回（swap）一个大数，继续向前走，直到数组结束）
public class twoFlag {
public static void partition(int []arr,int num) {
int less=-1;//小于等于区域的标记
for(int i=0;i<arr.length;i++)
{
if(arr[i]<=num)
swap(arr,i,++less);
else continue;
}
}
private static void swap(int[] arr, int i, int j) {
int t;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void main(String[] args)
{
int[]arr={1,50,20,67,69,82,11,3,59,70,3,4,2,11,0};
partition(arr,50);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}输出结果：1 50 20 11 3 3 4 2 11 0 82 67 69 59 70
荷兰国旗问题：
（三切分）给定一个数组arr和一个数num,让大于这数的数字放在数组的右边，小于这个数字放在数组的左边。 等于这个数的放数组中间。要求：时间复杂度O（n），额外空间复杂度O(1)
思路：在此处使用两个flag分别为less，more标记小于这个数的区域，大于这个数的区域，从而切分成三部分。less初始值在数组第一个数的左边（小于区域的终止位置），more初始值在数组最后一个属的后面，大于区域的第一个位置。
数组从第一个数开始遍历，判断，遍历到i位置时，如果小于num，此数与小于区域位置后一个数交换（swap（a[++less],a[i]）然后i++）如果大于num'，swap（a[i],a[--more]）然后便利指针停仍留在i位置（此时的i位置为从后面交换过来的数，并不知道其与num的大小，所以继续比较，i不进行++）直到遍历指针与more指针相遇（more指向第一个大于区域的数）遍历停止。
public class FlagSort {
public static void partition(int arr[],int num) {
int i=0;
int less=-1;
int more=arr.length;
while(i<more) {
if(arr[i]<num)
swap(arr,i++,++less);
else if(arr[i]>num)
swap(arr,i,--more);
else//相等
i++;
}
}
//传入数组进去，进行交换的是arr[i],arr[j]，如果只传入两个数，是达不到交换目的的（函数中型参与实参的区别）
private static void swap(int [] arr,int i, int j) {
int t;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void main(String[] args)
{
int[]arr={1,50,20,67,69,82,11,3,59,70,3,4,2,11,0};
partition(arr,50);
for(int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}进行荷兰国旗的分配之后，结果为：1 20 0 11 2 11 3 4 3 50 70 59 82 69 67
（用for循环）
public static void partition2(int arr[],int num) {
int less=-1;
int more=arr.length;
for(int i=0;i<arr.length;i++) {
if(i==more) break;
if(arr[i]<num)
swap(arr,i,++less);
else if(arr[i]==num)
continue;
else if(arr[i]>num)
{
swap(arr,i,--more);
i--;
}
}
}经典快排：
选取第一个数（或最后一个数）作为基准,把它放在数组的中，数组一分为二，左边的数比它小右边的数比它大 ·将左边的部分递归 ·将右边的部分递归
public class quickSort {
public static void QuickSort(int[] A,int p,int r){//p,r分别为数组的首元素和尾元素下标
if (p<r){
int q=Partition(A,p,r);//划分数组，找到首元素A[p]在排好序后的位置q
swap(A,p,q);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
public static void swap(int[] arr,int a,int b){
int tem=arr[a];
arr[a]=arr[b];
arr[b]=tem;
}
public static int Partition(int []A,int p,int r){
/*
输入：数组A[p,r];
输出:j,,A的首元素在排好序的数组中的位置
*/
int key=A[p];
int i=p;
int j=r;
while (i<j){
/*从左向右遍历*/
while (A[i]<=key){
i=i+1;
}
/*从右向左遍历*/
while(A[j]>key){
j=j-1;
}
if (i<j){
swap(A,i,j);
}
}
return j;
}
---------------------
作者：漫步_云端
来源：CSDN
原文：https://blog.csdn.net/u013521296/article/details/81624085
版权声明：本文为博主原创文章，转载请附上博文链接！荷兰国旗改进后的快排（三切分）
分为三个区域，对小于区域递归，对大于区域递归（以最后一个数为标准切分）
public class QuickSort {
public static void quickSort(int arr[],int l,int r) {
if(l<r) {
int p[]=partition(arr,l,r);
quickSort(arr,l,p[0]);
quickSort(arr,p[1],r);
}
}
//切分（二切分）
public static int [] partition(int arr[],int l,int r) {
//arr[r]位置是对比的数据，先占用大于区域的第一个数
//(l,r时传入的数组的头部和尾部)
int less=l-1;
int more=r;
int i=l;
while(i<more)
{
if(arr[i]<arr[r])
swap(arr,i++,++less);
else if(arr[i]==arr[r])
i++;
else
swap(arr,i,--more);
}
swap(arr,r,more++);
//返回小数尾部，大数头部
return new int[] {less,more};
}
private static void swap(int [] arr,int i, int j) {
int t;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void main(String[] args) {
int[]arr={40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
quickSort(arr,0,arr.length-1);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
运行结果：0 1 3 5 8 9 40 50 50 51 60 70 81 100 500
随机快排（对比位置是随机选取的）
在数组中随机选取一个数，将其与最后一个数交换，然后将交换后的新的最后一个数为基准进行切分，递归。
相对于荷兰国旗改进后的排序加了一行随机选数语句
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
（partition关于返回值）代码多是返回等于区域的起始位置和终止位置，所以是++less与--more（其他代码中的more位置）（个人觉得都可以）我的代码是返回小于区域最后一个数的位置，大于区域第一个数的位置。
可能不存在小于区域或者大于区域，这样，返回值就是l-1或r+1，在下次递归时不满足（l<r）被过滤掉
//经典快排
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int arr[],int l,int r) {
if(l<r) {
//随即快排加了一条语句：
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int p[]=partition(arr,l,r);
quickSort(arr,l,p[0]);
quickSort(arr,p[1],r);
}
}
//切分（二切分）
public static int [] partition(int arr[],int l,int r) {
//arr[r]位置是对比的数据，先占用大于区域的第一个数
//(l,r时传入的数组的头部和尾部)
int less=l-1;
int more=r;
int i=l;
while(i<more)
{
if(arr[i]<arr[r])
swap(arr,i++,++less);
else if(arr[i]==arr[r])
i++;
else
swap(arr,i,--more);
}
swap(arr,r,more++);
//返回小数尾部，大数头部
return new int[] {less,more};
}
private static void swap(int [] arr,int i, int j) {
int t;
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
public static void main(String[] args) {
int[]arr={40,3,50,500,9,0,60,70,50,51,81,1,5,8,100};
quickSort(arr,0,arr.length-1);
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
在大量数据下：
时间复杂度：O（NLogN）
随机快排 额外空间复杂度O（logN）（partition返回的lr需要存放空间，然而lr是可以复用的，在复用的情况下，一层层递归下去，分logn层，所以空间复杂度为logn，在最差的情况只有左节点，会分n层，复杂度为O（n）但是我们以一般情况为标准）
工程上快排是最常用的排序，
优于归并排序，递归过程中，快排的常数项为N只用遍历一遍，归并需要开辟一个数组，额外空间复杂度为O（N）并且merge过程中还需要再拷贝回原数组，遍历了两遍。合并排序更占用空间和时间。
由上述运行结果得知，快排并不能做到稳定性，如果想要深究，并做到partition过程达到稳定性，可以查询 01 stable sort