java快排 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};
}