一，思想描述：

何谓挖坑法？我们来看一看详细过程。

给定原始数列如下，要求从小到大排序：
image.png

首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素：
image.png
接下来，从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。

在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来所在的位置成为了新的坑。同时，left向右移动一位。
image.png
此时，left左边绿色的区域代表着小于基准元素的区域。

接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。

在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。
image.png
此时，right右边橙色的区域代表着大于基准元素的区域。

下面按照刚才的思路继续排序：
8>4，元素位置不变，right左移
image.png
2<4，用2来填坑，left右移，切换到left。
image.png
6>4，用6来填坑，right左移，切换到right。
image.png
3<4，用3来填坑，left右移，切换到left。
image.png
5>4，用5来填坑，right右移。这时候left和right重合在了同一位置。
image.png
这时候，把之前的pivot元素，也就是4放到index的位置。此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。
image.png
image.png
image.png

二，代码演示—以首位元素为基准值：

  1. public class KuaiPai13 {
  3.   public static void main(String[] args) {
  4.         int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
  5.         quickSort(arr, 0, arr.length - 1);
  6.         System.out.println(Arrays.toString(arr));
  7.   }
  9.   /**
  10.    * 快速排序--挖坑法
  11.    * @param arr 数组
  12.    * @param startIndex 左边界索引
  13.    * @param endIndex 右边界索引
  14.    */
  15.   public static void quickSort(int[] arr, int startIndex, int endIndex) {
  16.         // 递归结束条件：startIndex大等于endIndex的时候
  17.         if (startIndex >= endIndex) {
  18.               return;
  19.         }
  20.         // 得到基准元素位置
  21.         int pivotIndex = partition(arr, startIndex, endIndex);
  22.         // 用分治法递归数列的两部分
  23.         quickSort(arr, startIndex, pivotIndex - 1);
  24.         quickSort(arr, pivotIndex + 1, endIndex);
  25.   }
  27.   /**
  28.    * 具体每一轮的快速排序：
  29.    * @param arr 数组
  30.    * @param startIndex 左边界索引
  31.    * @param endIndex 右边界索引
  32.    * @return 返回基准值的位置，此时基准值左边的元素都小于基准值，基准值右边的元素都大于基准值
  33.    */
  34.   private static int partition(int[] arr, int startIndex, int endIndex) {
  35.         // 取第一个位置的元素作为基准元素
  36.         int pivot = arr[startIndex];
  37.         // 初始化坑的位置，初始等于pivot基准值的位置
  38.         int kengIndex = startIndex;
  39.         //初始化左右游标/指针
  40.         int leftYb = startIndex;
  41.         int rightYb = endIndex;
  42.         //大循环在左右指针重合时结束
  43.         while ( leftYb<rightYb ) {
  44.               //right指针从右向左进行比较
  45.               // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
  46.               while ( leftYb<rightYb) {
  47.                     // 先遍历右边，
  48.                     //  如果元素大于基准值--右游标左移：
  49.                     if (arr[rightYb] >= pivot) {
  50.                           rightYb--;
  51.                     }else{ //如果右边的当前元素小于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
  52.                           arr[kengIndex] = arr[rightYb];
  53.                           kengIndex = rightYb;
  54.                           leftYb++;
  55.                           break;
  56.                     }
  57.               }
  58.               //再遍历左边，
  59.               // leftYb<rightYb ，左游标永远小于右游标，是遍历元素并发生元素变动的前提：
  60.               while (leftYb<rightYb) {
  61.                     //如果元素小于基准值--左游标右移，
  62.                     if (arr[leftYb] <= pivot) {
  63.                           leftYb++;
  64.                     }else{  //如果左边的当前元素大于基准值了，那么将该元素填入坑中，该元素本来的位置成为新的坑；
  65.                           arr[kengIndex] = arr[leftYb];
  66.                           kengIndex = leftYb;
  67.                           rightYb--;
  68.                           break;
  69.                     }
  70.               }
  71.         }
  72.         //跳出了大循环，说明此时此刻左右游标是重合的，这时将基准值放在重合位置(最后一个坑)，
  73.         // 此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
  74.         arr[kengIndex] = pivot;
  75.         return kengIndex;
  76.   }
  79. }

三，随机选取基准值—代码演示：

对于快速排序来说，最简单的方式是选择数列的第一个元素，这种选择在绝大多数情况是没有问题的。
但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？
当数据有序逆序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差，如果每一轮快排都是如此，那么时间复杂度为n^2。
随机选择基准 可以降低逆序带来的O(n^2)复杂度的可能性。

基准选择的三种方式：

  1. 固定基准 （比如第一个），当原始序列或子序列逆序时，复杂度接近O(n^2)，所以应该避免使用这种方式。
  2. 随机选择 ，降低了逆序复杂度变高的可能性，但仍然不容乐观。
  3. 三数取中，随机选择三个数，取中间大小的作为基准，当然，本身三个数都是不确定的，随机选择无意义，直接取原始数列的头、中、尾三个元素，得出中间大小作为基准即可。进一步降低了数列逆序的可能性。

可以看到，即使是性能最差的 固定基准 ，也不一定是 选择第一个元素作为基准 ，所以，我们应该掌握的快排，是不以第一个元素为基准的快速排序。

既然，以 第一个元素为基准的快速排序 ，理解和代码实现都是最简单的，那么我们为什么不这样写呢？

无论你使用了哪种 基准选择 的方式，在 元素移动 之前，你都可以让你的 基准 先与 第一个元素 进行 交换，这样是不是就变成了你手到擒来的快速排序？

所以你需要记住快速排序的总过程是：

  • 选择基准
  • 与第一元素交换
  • 元素移动

通过代码分析，我们得出结论，当 随机选择基准 时，无论

  • 挖坑法，增加判断条件
  • 指针交换法，影响指针优先移动顺序

都会增加代码复杂度，甚至，循环判断降低了代码性能。不妨，将复杂问题简单化，统一快速排序的过程。

  • 选择基准
  • 与第一元素交换
  • 元素移动
  1. /**
  2. * 快速排序--挖坑法：
  3. *           1，任意选择一个数作为基准值，
  4. *           2，将基准值与首位元素进行交换，
  5. *           3，基准值所在的位置成为原始坑kengIndex；
  6. *           4，先遍历右边，如果元素大于基准值--右游标左移，如果元素小于基准值--将该元素填入坑中，该元素本来的位置成为新的坑；
  7. *           5，再遍历左边，如果元素小于基准值--左游标右移，如果元素大于基准值--将该元素填入坑中，该元素本来的位置成为新的坑；
  8. *           6，直到左右游标重合，这时将基准值放在重合位置(最后一个坑)，此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
  9. *           7，递归调用该方法；
  10. * @param arr
  11. * @param leftIndex
  12. * @param rightIndex
  13. */
  14. public static void quicksort2(int[] arr, int leftIndex, int rightIndex) {
  15.     //初始化左右游标：
  16.     int leftYb = leftIndex;
  17.     int rightYb = rightIndex;
  18.     //随机选择一个数作为基准值：
  19.     //一般简单的来说都选择第一个数即可，但是存在逆序情况导致效率极低的风险；
  20.     // 随机选择的元素的位置：
  21.     int suijiIndex = (leftIndex + rightIndex) / 2; //基准值所在位置为原始坑位；
  23.     //我们将基准值和首位元素交换位置：
  24.     int temp = arr[suijiIndex];
  25.     arr[suijiIndex] = arr[leftIndex];
  26.     arr[leftIndex] = temp;
  28.     //基准值和首位元素交换位置之后，坑位位置为首位，基准值在首位；
  29.     int kengIndex = leftIndex;
  30.     int pivotVal = arr[kengIndex]; //基准值
  32.     //左游标永远小于右游标，是遍历元素并发生元素变动的前提：
  33.     while (leftYb < rightYb) {
  34.           //先遍历右边，
  35.           //如果元素大于基准值--右游标左移：
  36.           while (leftYb < rightYb && arr[rightYb] >= pivotVal) {
  37.                 rightYb--;
  38.           }
  39.           //跳出了循环，说明此时的右游标所在元素小于基准值，那么将该元素填入坑中，该元素本来的位置成为新的坑；
  40.           arr[kengIndex] = arr[rightYb];
  41.           kengIndex = rightYb;
  43.           //再遍历左边，
  44.           //如果元素小于基准值--左游标右移，
  45.           while (leftYb < rightYb && arr[leftYb] <= pivotVal) {
  46.                 leftYb++;
  47.           }
  48.           //跳出了循环，说明此时的左游标所在元素大于基准值，那么将该元素填入坑中，该元素本来的位置成为新的坑；
  49.           arr[kengIndex] = arr[leftYb];
  50.           kengIndex = leftYb;
  51.     }
  52.     //跳出了大循环，说明此时此刻左右游标是重合的，这时将基准值放在重合位置(最后一个坑)，此时，基准值左边的元素都小于基准值，基准值右边的元素都大于基准值，这一轮交换宣告结束；
  53.     arr[kengIndex] = pivotVal;
  55.     //递归调用：
  56.     if (leftYb - 1 > leftIndex) {
  57.           quicksort2(arr, leftIndex, kengIndex - 1);
  58.     }
  59.     if (rightIndex > rightYb + 1) {
  60.           quicksort2(arr, kengIndex + 1, rightIndex);
  61.     }
  63. }

image.png