根据荷兰国旗问题引出的快速排序

荷兰国旗问题:

荷兰国旗有三横条块构成，自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要求将所有红色的条块放最左边、所有白色的条块放中间、所有蓝色的条块放最右边。

有一个数组，输入一个数num，把小于这个数的放左边，等于这个数的放在中间，大于这个数的放右边。

假设有一个数组arr{12,3,2,4,2,6,4}。我们输入一个数4。把小于部分的xia'下标用less表示，大于部分的用more表示，整个数组下标用cur表示。当cur下标指向的数组的值小于数num的时候，less有右移一位，然后和cur指向的数交换，cur++；当cur下标指向的数组的值大于数num，more左移一位，然后会cur指向的数jiao交换，cur这是不操作，因为此时more的数不能确定数字的大小。如果上述都不满足cur++；结束的条件是当cur和more相碰；

下面看代码：

package com.Quik;

public class HelangFlage {
	/*
	 * 荷兰国旗问题
	 */
	public static void process(int[]arr,int num){
		if(arr==null && arr.length<2){
			return ;
		}
		process(arr,0,arr.length - 1,num);
	}
	public static void process(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){
				 swpe(arr,++less,cur++);
			 }else if(arr[cur]>num){
				 swpe(arr,--more,cur) ;
			 }else{
				 cur++ ;
			 }
		 }
	}
	public static void swpe(int[] arr , int i, int  j ){
		int temp = arr[i] ;
		arr[i] = arr[j] ; 
		arr[j] = temp ;
	}
	public static void main(String[] args) {
		int[] arr = new int []{3,1,2,4,5,10,10,4,65,32,45,123,65} ;
		process(arr,65);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+",");
		}
	}
}

那么快速排序是什么呢？

快速排序就是没有自己输入的num值作为参考。而是以数组arr的最后一个数作为参考。当一个循环结束的时候把这个数和more下标的值交换。排序完成。

下面看代码

package com.Quik;

public class QuiklySot {
	public static void QuikSort(int[] arr){
		if(arr==null && arr.length < 2){
			return  ;
		}
		QuikSort(arr, 0, arr.length - 1);
	}
	
	
	public static void QuikSort(int[] arr,int L,int R){
		if(L<R){
			int[] flage = process(arr, L, R);
			QuikSort(arr, L, flage[0]-1);
			QuikSort(arr, flage[1]+1, R);
		}
		
	}
	public static int[] process(int[] arr ,int L, int R){
		int less = L - 1 ; 
		int more = R ;  //选取数组最后一个数作为参考，循环过程不动
		int cur = L ;
		while(cur<more){
			if(arr[cur]<arr[R]){
				swpe(arr, ++less, cur++);
			}else if(arr[cur]>arr[R]){
				swpe(arr, --more, cur);
			}else{
				cur++;
			}
		}
		swpe(arr, more, R); //arr[R]和arr[more]交换
		return new int[]{less+1,more} ; //返回等于arr[R]的第一个下标less+1和最后一个下标more
	}
	public static void swpe(int[] arr ,int i,int j ){
		int temp = arr [i] ;
		arr[i] = arr[j] ;
		arr[j] = temp ;
	}
	public static void main(String[] args) {
		int[] arr = new int[]{13,34,1234,1,234,2,34,134,456,67,345,23} ;
		QuikSort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+",");
		}
	}
}