4.快速排序法

如果允许开额外空间

原地完成

如果e>v,直接i++
如果e
最后交换e与v

public class QuickSort {
    private QuickSort() {
    }
    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }
    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        //arr[l+1,j] <v      arr[j+1,i) >=v
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, l, j);
        return j;
    }
    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

非递归

  //非递归实现  
   private static void quickSort(int[] array) {
      if (array == null || array.length == 1) {
          return;
      }
      //存放开始于结束索引
      Stack<Integer> stack = new Stack<>();
      stack.push(0);
      stack.push(array.length - 1);
      //循环读取栈中的开始结束位置
      while (!stack.isEmpty()) {
          int right = stack.pop();
          int left = stack.pop();
          //右边界索引小于左边界索引说明结束了
          if (left >= right) {
              continue;
          }
          int i = partition(array, left, right);
          if (left < i - 1) {
              stack.push(left);
              stack.push(i -  1);
          }
          if (i + 1 < right) {
              stack.push(i + 1);
              stack.push(right);
          }
      }
  }
private static  int partition(int[] arr, int l, int r) {
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < arr[l]) {
            j++;
            swap(arr, i, j);
        }
    }
    swap(arr, l, j);
    return j;
}