一，思想描述：

给定原始数列如下，要求从小到大排序：
image.png
一开始和挖坑法相似，我们首先选定基准元素Pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素：

接下来是第一次循环，从right指针开始，把指针所指向的元素和基准元素做比较。如果大于等于pivot，则指针向左移动；
如果小于pivot，则right指针停止移动，切换到left指针。

轮到left指针行动，把指针所指向的元素和基准元素做比较。如果小于等于pivot，则指针向右移动；
如果大于pivot，则left指针停止移动。

这时候，我们让left和right指向的元素进行交换.

接下来，我们进入第二次循环、第三次循环…，

进入最后一次循环，right移动到元素x停止，这时候请注意，left和right指针已经重合在了一起。

当left和right指针重合之时，我们让pivot基准值元素和left指针与right指针重合点的元素进行交换。
此时数列左边的元素都小于4，数列右边的元素都大于4，这一轮交换终告结束。

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

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

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

对于快速排序来说，最简单的方式是选择数列的第一个元素，这种选择在绝大多数情况是没有问题的。

但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？

当数据有序逆序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差，如果每一轮快排都是如此，那么时间复杂度为n^2。

随机选择基准 可以降低逆序带来的O(n^2)复杂度的可能性。

基准选择的三种方式：

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

可以看到，即使是性能最差的 固定基准 ，也不一定是 选择第一个元素作为基准 ，所以，我们应该掌握的快排，是不以第一个元素为基准的快速排序。
既然，以 第一个元素为基准的快速排序 ，理解和代码实现都是最简单的，那么我们为什么不这样写呢？
无论你使用了哪种 基准选择 的方式，在 元素移动 之前，你都可以让你的 基准 先与 第一个元素 进行 交换，这样是不是就变成了你手到擒来的快速排序？

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

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

通过代码分析，我们得出结论，当 随机选择基准 时，无论是挖坑法还是指针交换法，都会增加代码复杂度，甚至，循环判断降低了代码性能。

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

不妨，将复杂问题简单化，统一快速排序的过程

  • 选择基准
  • 与第一元素交换
  • 元素移动
  1. /**
  2. * 快速排序 -- 指针交换法
  3. * @param arr        数组
  4. * @param leftIndex  数组的左边下标索引
  5. * @param rightIndex 数组的右边下标索引
  6. */
  7. public static void quicksort(int[] arr, int leftIndex, int rightIndex) {
  8.     //    初始化左右游标：
  9.     int leftYouBiao = leftIndex;
  10.     int rightYouBiao = rightIndex;
  11.     //随机找一个基准值：
  12.     int randomIndex = RandomUtils.nextInt(leftIndex, rightIndex + 1);
  13.     //简单起见，不徒增复杂度，将当前基准值和数组首位元素互换位置：
  14.     int temp = arr[randomIndex];
  15.     arr[randomIndex] = arr[leftIndex];
  16.     arr[leftIndex] = temp;
  18.     //初始化交换位置之后的基准值：
  19.     int pivoltVal = arr[leftIndex];
  20.     int pivoltIndex = leftIndex;
  22.     //开始循环遍历数组，左边比中轴值大的和右边比中轴值小的对调：
  23.     while (leftYouBiao < rightYouBiao) {
  24.           //先遍历右边：
  25.           //右边比中轴值大的，略过：
  26.           while (leftYouBiao < rightYouBiao && arr[rightYouBiao] >= pivoltVal) {
  27.                 rightYouBiao--;
  28.           }
  29.           //左边比中轴值小的，略过：
  30.           while (leftYouBiao<rightYouBiao && arr[leftYouBiao] <= pivoltVal) {
  31.                 leftYouBiao++;
  32.           }
  33.           //上边两个循环已经过去，
  34.           // 1，此时说明左游标所在位置元素大于中轴值、右游标所在位置元素小于中轴值：
  35.           if (leftYouBiao < rightYouBiao) {
  36.                 //   此时，对调元素：
  37.                 int temp2 = arr[leftYouBiao];
  38.                 arr[leftYouBiao] = arr[rightYouBiao];
  39.                 arr[rightYouBiao] = temp2;
  40.           }
  41.     }
  42.     //此时，跳出大循环，说明此时左右游标重合，将基准值与重合位置元素对调：
  43.     int temp3 = arr[pivoltIndex];
  44.     arr[pivoltIndex] = arr[leftYouBiao];
  45.     arr[leftYouBiao] = temp3;
  47.     //递归调用：
  48.     if (leftYouBiao - 1 > leftIndex) {
  49.           quicksort(arr, leftIndex, leftYouBiao-1);
  50.     }
  51.     if (rightIndex  > rightYouBiao+1) {
  52.           quicksort(arr, rightYouBiao+1, rightIndex );
  53.     }
  54. }

牛客网测试：
image.png

四，为什么最后要将基准值和重合位置元素进行交换呢？

指针交换法，为什么最后将基准值和重合位置元素进行交换呢？

疑问：基准值在首位，如果重合位置元素大于基准值，和处在首位的基准值交换之后，那么该大于基准值的重合位置元素岂不是在了基准值的左边？这就不符合快速排序了？

答：先说结论，重合位置的元素一定是小于基准值的。
因为代码中，每一次交换完元素之后，都是右指针先开始左移遍历，只有右指针遇到小于基准值元素停下之后，才开始左指针右移遍历。

所以，左右指针重合有两种情况：

1，右指针不动、左指针追上了右指针；

这种情况是：上一次交换完元素之后，右指针率先进行了左移遍历，然后遇到了小于基准值元素之后停下，然后左指针开始右移遍历，
左指针右移遍历，一路上都是小于基准值的元素，所以左指针一路无阻，一直追上了右指针，两指针重合；

2，左指针不动，右指针追上了左指针；

这种情况是：上一次交换完元素之后，右指针率先再次进行了左移遍历，一路上都是大于基准值的元素，所以右指针一路无阻，一直追上了上一次交换完元素之后压根还没动的左指针。

3，总结：

对于第一种情况，右指针不动、左指针追上了右指针，此时，重合的位置一定是右指针遇到了小于基准值的元素了的位置，所以此时的重合位置的元素一定是小于基准值的，
此时基准值在首位，所以重合位置元素和基准值交换完之后，该重合位置元素一定在基准值左边。
对于第二种情况，左指针不动，右指针追上了左指针，此时，左指针是上一次刚刚交换过位置的、原本是处在右边的小于基准值的那个元素，
所以此时重合位置的元素，即左指针所在位置的元素，也一定是小于基准值的，所以和基准值交换完之后，该处在重合位置且小于基准值的元素也一定在基准值的左边。
·
·