Java經典快排思想以及快排的改進講解

public static void NetherlandsFlag(int[] arr, int L, int R, int num) {
 int i = L;
 int p1 = L-1;
 int p2 = R+1;
 //終止條件：當前數的位置在大于區的前一個
 while(i < p2) {
  if(arr[i] < num) {
   //當前數比num小，放左邊，i位置上的數和L上的數進行交換，并且i++，L++
   swap(arr, i++, ++p1);
  } else if(arr[i] == num) {
   //當前數和num相等，i++
   i++;
  } else {
   //當前數比num大，放右邊，i位置上的數和R上的數進行交換，并且i++，R--
   swap(arr, i, --p2);
  }
 }
}

/*
 * swap(int[] arr, int i, int j);是將arr數組的i和j位置上的數交換的方法
 */
public static void quickSort(int[] arr) {
 // 如果為空或長度為1不需要排序，直接返回
 if(arr == null || arr.length < 2)
  return;
 else
  quickSort(arr, 0, arr.length - 1);
}
// 遞歸排序
public static void quickSort(int[] arr, int L, int R) {
 if(L < R) {
  /*
   * 隨機快排的隨機就在這
   * 是隨機選取了一個數，和 R 進行了交換，然后使用這個數作為num，
   * 所以每次選取的num是隨機的，
   * 在計算時間復雜度時，是沒有最優最差情況的
   * 而是通過一個長期的數學期望計算的，結果是O(N*logN)
   */
  swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
  int[] border = partition(arr, L, R);
  // 小于區和大于區進行遞歸
  quickSort(arr, L, border[0] - 1);
  quickSort(arr, border[1] + 1, R);
 }
}
// 將給定數組劃分為小于區、等于區和大于區
public static int[] partition(int[] arr, int L, int R) {
 int num = arr[R];
 int less = L - 1;
 int more = R + 1;
 int curr = L;
 // 分為小于區等于區和大于區
 while(curr < more) {
  if(arr[curr] < num) {
   swap(arr, curr++, ++less);
  } else if(arr[curr] > num) {
   swap(arr, curr, --more);
  } else {
   curr++;
  }
 }
 //返回等于區的左右邊界的下標，通過下標確定小于區和大于區遞歸時的參數
 return new int[] {less + 1, more - 1};
}