優化經典快排

問題1：給定一個數組arr， 和一個數num， 請把小于等于num的數放在數組的左邊， 大于num的數放在數組的右邊。要求額外空間複雜度O(1)， 時間複雜度O(N)。

public class a {
    public static void partition (int[] arr, int num) {
        int left = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < num) {
                swap(arr, ++left, i);
            }
        }
    }
    public static void swap(int[] arr, int index, int position) {
        int temp = arr[index];
        arr[index] = arr[position];
        arr[position] = temp;
    }
}
           

問題2:（荷蘭國旗問題）

給定一個數組arr， 和一個數num， 請把小于num的數放在數組的左邊， 等于num的數放在數組的中間， 大于num的數放在數組的右邊。要求額外空間複雜度O(1)， 時間複雜度O(N).

public class NetherlandsFlag {

	public static int[] partition(int[] arr, int l, int r, int num) {
		int less = l - 1;
		int more = r + 1;
		while (l < more) {
			if (arr[l] < num) {
				swap(arr, ++less, l++); // 将目前與小于區域的下個位置交換
			} else if (arr[l] > num) {
				swap(arr, --more, l);  // 大于區域的前一個數與目前交換
			} else {  // == num
				l++;
			}
		}
		return new int[] { less + 1, more - 1 };  // less+1是等于區域的第一個位置，more-1是等于區域的最後一個位置。
	}
}
           

問題3：改進後快排

• 改進1：使用随機選取劃分點，避免極端情況（已經有序）。
• 改進2：使用荷蘭國旗問題優化快排，使等于劃分數不再繼續參與劃分，避免無效排序。

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] - 1);  // 繼續左邊
			quickSort(arr, p[1] + 1, r);  // 繼續右邊
		}
	}

	public static int[] partition(int[] arr, int l, int r) {  // 以arr[r]數字劃分
		int less = l - 1;
		int more = r;
		while (l < more) {
			if (arr[l] < arr[r]) {
				swap(arr, ++less, l++);
			} else if (arr[l] > arr[r]) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		swap(arr, more, r); // more是指向大于區域的第一個大于arr[r]的數，最後需要将劃分數調整到劃分位置。
		return new int[] { less + 1, more };  // 傳回中間等于區域的首尾邊界
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}