Java經(jīng)典快排思想以及快排的改進講解

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

/*
 * swap(int[] arr, int i, int j);是將arr數(shù)組的i和j位置上的數(shù)交換的方法
 */
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) {
  /*
   * 隨機快排的隨機就在這
   * 是隨機選取了一個數(shù)，和 R 進行了交換，然后使用這個數(shù)作為num，
   * 所以每次選取的num是隨機的，
   * 在計算時間復(fù)雜度時，是沒有最優(yōu)最差情況的
   * 而是通過一個長期的數(shù)學(xué)期望計算的，結(jié)果是O(N*logN)
   */
  swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
  int[] border = partition(arr, L, R);
  // 小于區(qū)和大于區(qū)進行遞歸
  quickSort(arr, L, border[0] - 1);
  quickSort(arr, border[1] + 1, R);
 }
}
// 將給定數(shù)組劃分為小于區(qū)、等于區(qū)和大于區(qū)
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;
 // 分為小于區(qū)等于區(qū)和大于區(qū)
 while(curr < more) {
  if(arr[curr] < num) {
   swap(arr, curr++, ++less);
  } else if(arr[curr] > num) {
   swap(arr, curr, --more);
  } else {
   curr++;
  }
 }
 //返回等于區(qū)的左右邊界的下標(biāo)，通過下標(biāo)確定小于區(qū)和大于區(qū)遞歸時的參數(shù)
 return new int[] {less + 1, more - 1};
}