1. 前言

排序算法是数据结构中最基础的算法，快速排序则是面试中最常见的排序算法。无论是校招面试还是社招面试，快速排序算法的出现频率远高于其他算法，而且经常会要求候选人白板手写实现算法。快速排序算法的核心是分治处理，重点是分析时间复杂度。

2. 快速排序算法

面试官提问：快速排序算法是怎么实现的？能手写实现一个快排算法吗？

题目解析：

为了实现bug free（基本没有逻辑缺陷）的白板编程，候选人可以将解决这个题目的过程分为两个步骤：

（1）分析快速排序算法的步骤，并且编码实现；
（2）完成编码后，使用一个小规模的数据作为测试样例，模拟算法流程验证代码逻辑是否符合预期。

2.1 快速排序步骤

快速排序算法的核心是分治算法，所谓分治（Divide and Conquer）就是将一个复杂的问题分成两个或者多个相同或者相似的子问题，再把这些子问题分成多个相同或者相似的子问题，直到子问题能够被简单求解，把子问题的解合起来就是原始问题的解。

快排的分治思维在于将大的数组拆分为两个需要排序的左右子数组，再对子数组套用相同算法，直到子树组只有一个数字，一个数字的数组本身就是有序的，构成了原子问题的解。快排的核心步骤拆分为：

（1）选择基准：对于数组 A，选择一个数字作为基准值（pivot），习惯选择数组第一个元素作为 pivot；
（2）构造分区：定义 left 和 right 左右指针，将小于基准的元素移动到左边，将大于基准的元素移动到右边；
（3）递归求解：对于基准左边的数组 A1、基准右边的数组 A2 重复第一步和第二步，直到所有的子树组已经满足排序性质（子数组为空或者子树组只有一个元素）。

快速排序的算法实现代码以及解析，示例：

    public void quicksort(int[] A,int left, int right) {
        //1. 递归终止条件，如果不构成数组结束算法
        if(left > right)
            return;
        int i, j, t, pivot;
        //2. 选择第一个元素作为pivot
        pivot = A[left];
        i = left;
        j = right;
        while(i != j) {
            //3.1 这里要注意顺序，必须先从右边开始找到第一个比pivot小的数
            while(A[j] >= pivot && i < j)
                j--;
            //3.2 然后从左边找到第一个比pivot大的数字
            while(A[i] <= pivot && i < j)
                i++;
            //3.3 交换两个数在数组中的位置
            if(i < j) {
                t = A[i];
                A[i] = A[j];
                A[j] = t;
            }
        }
        //4. 最终将基准数归位
        A[left] = A[i];
        A[i] = pivot;
        //递归处理左边的分数组
        quicksort(A,left, i-1);
        //递归处理右边的分数组
        quicksort(A,i+1, right);
    }

2.2 小型数组模拟

下面我们使用一个小规模的数组模拟快速排序的过程，原始数组A的顺序是22、11、44、10、33。

（1）首先给定初始值：pivot = nums[left] = 22，left=0，right=4。

（2）从右到左找到 index=3 的位置，nums[3] 比 pivot 小；从左到右找到 index=2 的位置，nums[2] 比 pivot 大。

（3）交换坐标 i 和 j 所在的数组值。

（3）坐标 i 和 j 碰头，本次查找结束，交换 pivot 的值和 nums[i] 的值。

（4）本次查询完全结束，对坐标[0，1]的子数组和坐标[3，4]的子树组进行相同的递归操作，结束之后，数组A得到结果10、11、22、33、44。

2.3 快排考察点

关于快排，候选人需要注意几个关键的考察点：

（1）快排的平均时间复杂度为O（N*logN），最坏状态下时间复杂度为O（N^2），一般不会涉及具体的数学证明；
（2）快排不是稳定排序算法，例如原始数组存在两个相同的数值，排序可能会交换两个值的顺序；
（3）快速排序的核心思路是分治算法，实现方式是递归。

3. 小结

本章节介绍了面试最常见的排序算法算法：快排的算法思路以及使用 Java 实现了一个快排的算法模板。候选人可以使用小规模的数组测试现场编写的算法是否符合预期，特别需要注意快排的时间复杂度。