一、荷兰国旗问题

在讲快速排序前，我们先来看看荷兰国旗问题。题目如下：

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

其实，这就是快排的partition过程，通过三个指针，index，less，more进行的，初始less=左边界-1，more=右边界+1，说明一开始不存在less域和more域：
1）若arr[index] < num，less域增加，即less++，然后index和less位置的数交换后，index++继续指向下一个数
2）若arr[index] > num，more域增加，即more++，然后index和more的数交换后，继续判断交换后arr[index]和num的关系
3）若arr[index] == num，index++继续指向下一个数，不坐任何处理
4）重复以上过程，直至index==more

大致过程图：

代码实现

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;
  }

二、经典快速排序

快排其实是冒泡排序的改进，其算法思路如下：
1）在数组中选取一个数作为基准元素
2）分区，把小于基准的数放左边，大于基准的数放右边
3）递归，对左右两个分区重复以上步骤

在网上找了一张图，如下所示（侵删）：

实现代码

  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;
  }

三、改进的快速排序

回顾经典的快速排序，可以优化的地方有两个：

1）基准的选取，若每次取数组的第一个作为基准，则可能出现基准是数组中最小的数，造成了多余的计算。因此，基准的选取可以进行随机选择
2）分区返回的边界，回顾荷兰国旗问题，分区时，可以发现基准可以是中间一片区域，而不是一个数，因此，分区时，返回的不在是基准的位置，而是基准的左边界和右边界，那么下次划分子问题时，就可以减少交换的次数了。

代码实现

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;
  }