【算法】快速排序及优化

给定一个数组arr，和一个数num，请把
小于num的数放在数组的左边，
等于num的数放在数组的中间，
大于num的数放在数组的 右边。
要求额外空间复杂度O(1)，时间复杂度O(N)，
例如： 
对于数组3,5,4,5,8,1,9，以5进行分割
输出：3 4 1 5 5 9 8 

public static int[] partition(int[] arr, int l, int r, int num) {
    int less = l - 1;
    int more = r + 1;
    int index = l;
    // 循环至index到more相等
    while (index < more) {
      if (arr[index] < num) {
        // 扩大less域
        swap(arr, ++less, index++);
      }else if (arr[index] > num){
        // 扩大more域，且交换后，继续判断当前index的数和num的关系
        swap(arr, --more, index);
      }else {
        index++;
      }
    }
    int[] result = {less + 1, more - 1};
    // 返回相等区间开始和结束的索引值
    return result;
  }
  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
  }

  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) {
      return;
    }
    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
  }

  public static int partition(int[] arr, int l, int r) {
    // 取左边第一个数为基准
    int pivot = arr[l];
    int i = l;
    int j = r;
    while(i != j) {
      // 从右边找第一个小于基准的数
      while(arr[j] >= pivot && i < j) {
        j--;
      }
      // 从左边找第一个大于基准的数
      while(arr[i] <= pivot && i < j) {
        i++;
      }
      if (i < j) {
        swap(arr, i, j);
      }
    }
    // 将基准归位
    swap(arr, l, j);
    // 返回基准的位置
    return j;
  }

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    // quickSort2(arr, 0, arr.length - 1);
    quickSort(arr, 0, arr.length - 1);
  }

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
      // 从l~r中选一个数，放在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) {
    int less = l - 1;
    int more = r;
    int index = l;
    // 循环至index到more相等
    while (index < more) {
      if (arr[index] < arr[r]) {
        // 扩大less域
        swap(arr, ++less, index++);
      }else if (arr[index] > arr[r]){
        // 扩大more域，且交换后，继续判断当前index的数和num的关系
        swap(arr, --more, index);
      }else {
        index++;
      }
    }
    // 将基准归位，基准取的是最右边的数
    swap(arr, more, r);
    int[] result = {less + 1, more};
    // 返回相等区间开始和结束的索引值
    return result;
  }