快速排序并不难

本文介绍: 快速排序的核心框架是“二叉树的前序遍历+对撞型双指针”。我们在《一维数组》一章提到过”双指针思路“：在处理奇偶等情况时会使用两个游标，一个从前向后，一个是从后向前来比较，根据结果来决定继续移动还是停止等待。快速排序的每一轮进行的时候都是类似的双指针策略，而递归的过程本质上就是二叉树的前序递归调用。

快速排序的核心框架是“二叉树的前序遍历+对撞型双指针”。我们在《一维数组》一章提到过”双指针思路“：在处理奇偶等情况时会使用两个游标，一个从前向后，一个是从后向前来比较，根据结果来决定继续移动还是停止等待。快速排序的每一轮进行的时候都是类似的双指针策略，而递归的过程本质上就是二叉树的前序递归调用。

1 快速排序的基本过程

快速排序是将分治法运用到排序问题的典型例子
快速排序基本思想是：通过一个标记 pivot 元素将n个元素的序列划分为左右两个子序列 left和right，其中left中的元素都比pivot小，right的都比pi vo t的大，然后再次堆left和r i g ht各自再执行快速排序，在将左右子序列排好序之后，整个序列就有序了。这里排序进行左右划分的时候是一直划分到子序列只包含一个元素的情况，然后再递归返回。
我们以关键字序列{26,53,48,15,13,48,32,15}看一下一次划分的过程:

上面红框位置表示当前已经被赋值给了pi v o t或者其他位置，可以空出来放移动来的新元素了。我们可以看到26最终被放到了属于自己的位置上，不会再变化。而左侧的都比26小，左侧都比26大，因此26的左右两侧可以分别再进行排序。
这一轮过程是什么呢？就是数组增删的时候经常用的双指针策略，我们在数组部分讲过，不再赘述。而这里的每一轮都是一个相向的双指针而已，没有任何神秘的。
根据上述原理，我们可以写代码了，在实现过程中，为了方便实现，会对部分代码微调一下，详细代码如下：

//原文件QuickSortBasic.java
public static void quickSort(int[] arr, int left, int right) {
        if (left &lt; right) {
            int pivot = arr[right];
            int i = left - 1;
            for (int j = left; j &lt; right; j++) {
                if (arr[j] &lt; pivot) {
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            //哨兵移动到位置pivotIndex上
            int pivotIndex = i + 1;
            int temp = arr[pivotIndex];
            arr[pivotIndex] = arr[right];
            arr[right] = temp;

            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
}

2.第二种实现 方式

至于实现，有很多种方式，下面再给一种实现方式：

void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        //这里就是一个对撞的双指针操作
        int left = start, right = end;
        int pivot = array[(start + end) / 2];
        
        while (left <= right) {
            while (left <= right &amp;&amp; array[left] < pivot) {
                left++;
            }
            while (left <= right &amp;&amp; array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
                left++;
                right--;
            }
        }
        //先处理元素再分别递归处理两侧分支，与二叉树的前序遍历非常像
        quickSort(array, start, right);
        quickSort(array, left, end);   
    }