【資料結構】--【排序】--荷蘭國旗詳解

 * 荷蘭國旗：将給定一個數組arr，和一個數num，請把小于num的數放在數組的左邊，等于num的數放在數組的中間，大于num的數放在數組的右邊。

 *                     要求額外空間複雜度O(1)，時間複雜度O(N)

 * 思路：需要三個指針（小于num指針small、等于num指針equal、大于num指針big） 有以下三種情況

 *     1、cur小于num，samll指針加一，同時推動equal指針加一；

 *     2、cur等于num，equal指針加一，

 *     3、cur大于num，big指針值和cur指針的值交換，同時big指針加一，cur不用動。

注意：要想清楚循環條件中是哪兩個下标進行對比。

public class DutchFlag {

	public static void dutchFlag(int[] arr,int l,int r,int num){
		int small = l-1;
		int big =r+1;
		int cur=l;
//		while(cur<r){
		for(;cur<big;){
/*			在cur=5，big=6時候已經成功了，再往下就沒有意義了，反而會打亂已經正常的排序導緻最後錯誤結果為1，3，4，8，2，9，5，5，6，7
			是以選擇循環的條件很重要。應該是cur和big比較，而不是和r比較。
			注意while循環和for循環的差別。while循環中沒有增量，增量是在方法體内完成的，而for通常是有增量的，需要小心for循環的增量會影響代碼内的增量。
			錯誤for(;cur<big;cur++)正确  for(;cur<big;){
			主要是想好算法的中心*/
//			如果目前值比給定值小，則交換目前值和small指針指向的值，同時++
			if(arr[cur]<num){
				SimpleSorting.swap(arr,++small,cur++);
//			cur大于num，交換目前值和big指針指向的值，big--，因為還要在此判斷交換過的值，
			}else if(arr[cur]>num){
				SimpleSorting.swap(arr, cur, --big);
			}else{
//				cur等于num，equal指針加一，
				cur++;
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] arr = {1,3,5,7,9,5,2,4,6,8};
//		調用方法
		dutchFlag(arr,0,arr.length-1,5);
		for (int i : arr) {
			System.out.println(i);
		}
	}

}
           

各位大佬 我已經很認真畫了。