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。

index 0 1 2 3 4
数组值 22 11 44 10 33
指针 left right

(2)从右到左找到 index=3 的位置,nums[3] 比 pivot 小;从左到右找到 index=2 的位置,nums[2] 比 pivot 大。

index 0 1 2 3 4
数组值 22 11 44 10 33
指针 left i j right

(3)交换坐标 i 和 j 所在的数组值。

index 0 1 2 3 4
数组值 22 11 10 44 33
指针 left i,j right

(3)坐标 i 和 j 碰头,本次查找结束,交换 pivot 的值和 nums[i] 的值。

index 0 1 2 3 4
数组值 10 11 22 44 33
指针 left i,j right

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

2.3 快排考察点

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

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

3. 小结

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