此文章旨在暴力排序的基础上进行优化，能尽量减少特殊情况让排序的时间复杂度上升，比如特殊情况下快排将会变成冒泡排序。

注：下面所有的swap方法是交换数组俩个位置的值，因为很多地方都用到了，减少代码冗余。

1. 基本的排序算法

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）

2. 常考的排序算法

归并排序（Merge Sort）

快速排序（Quick Sort）

拓扑排序（Topological Sort）

3. 其他排序算法

堆排序（Heap Sort）

桶排序（Bucket Sort)

注意：

1.冒泡排序和插入排序是最基础的，面试官有时候喜欢拿它们来考察你的基础知识，并且看看你能不能快速地写出没有 bug 的代码。

2.归并排序、快速排序和拓扑排序的思想是解决绝大部分涉及排序问题的关键，我们将在这篇文章里重点介绍它们。

3.堆排序和桶排序，本节课不作深入研究，但有时间的话一定要看看，尤其是桶排序，在一定的场合中（例如知道所有元素出现的范围时），能在线性的时间复杂度里解决战斗，掌握好它的解题思想能开阔解题思路。

冒泡排序（Bubble Sort）

基本思想

给定一个数组，我们把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。

实现

每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。

例题分析

给定数组 [2, 1, 7, 9, 5, 8]，要求按照从左到右、从小到大的顺序进行排序。

解题思路

从左到右依次冒泡，把较大的数往右边挪动即可。

冒泡排序过程

1.首先指针指向第一个数，比较第一个数和第二个数的大小，由于 2 比 1 大，所以两两交换，[1, 2, 7, 9, 5, 8]。

2.接下来指针往前移动一步，比较 2 和 7，由于 2 比 7 小，两者保持不动，[1, 2, 7, 9, 5, 8]。到目前为止，7 是最大的那个数。

3.指针继续往前移动，比较 7 和 9，由于 7 比 9 小，两者保持不动，[1, 2, 7, 9, 5, 8]。现在，9 变成了最大的那个数。

4.再往后，比较 9 和 5，很明显，9 比 5 大，交换它们的位置，[1, 2, 7, 5, 9, 8]。

5.最后，比较 9 和 8，9 比 8 大，交换它们的位置，[1, 2, 7, 5, 8, 9]。经过第一轮的两两比较，9 这个最大的数就像冒泡一样冒到了数组的最后面。

接下来进行第二轮的比较，把指针重新指向第一个元素，重复上面的操作，最后，数组变成了：[1, 2, 5, 7, 8, 9]。

在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。

代码示例

void sort(int[] nums) {
    //定义一个布尔变量 hasChange，用来标记每轮遍历中是否发生了交换
    boolean hasChange = true; 

    //每轮遍历开始，将 hasChange 设置为 false
    for (int i = 0; i < nums.length - 1 && hasChange; i++) {
        hasChange = false;

        //进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生
        for (int j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                hasChange = true;
            }
        }
     }
 }

算法分析

空间复杂度

假设数组的元素个数是n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度

1. 给定的数组按照顺序已经排好

在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

2. 给定的数组按照逆序排列

在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。

3. 给定的数组杂乱无章

在这种情况下，平均时间复杂度是 O(n2)。

由此可见，冒泡排序的时间复杂度是O(n2)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。）

插入排序（Insertion Sort）

基本思想

不断地将尚未排好序的数插入到已经排好序的部分。

特点

在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。

例题分析

对数组 [2, 1, 7, 9, 5, 8] 进行插入排序。

解题思路

首先将数组分成左右两个部分，左边是已经排好序的部分，右边是还没有排好序的部分，刚开始，左边已排好序的部分只有第一个元素2。接下来，我们对右边的元素一个一个进行处理，将它们放到左边。

image

1.先来看 1，由于 1 比2小，需要将1插入到2的前面，做法很简单，两两交换位置即可，[1, 2, 7, 9, 5, 8]。

2.然后，我们要把 7 插入到左边的部分，由于7已经比2大了，表明它是目前最大的元素，保持位置不变，[1, 2, 7, 9, 5, 8]。

3.同理，9 也不需要做位置变动，[1, 2, 7, 9, 5, 8]。

4.接下来，如何把 5 插入到合适的位置。首先比较5和9，由于5比9小，两两交换，[1, 2, 7, 5, 9, 8]，继续，由于5比7小，两两交换，[1,2,5,7,9,8]，最后，由于 5 比 2 大，此轮结束。

5.最后一个数是 8，由于 8 比 9 小，两两交换，[1, 2, 5, 7, 8, 9]，再比较 7 和 8，发现 8 比 7 大，此轮结束。到此，插入排序完毕。

代码示例

void sort(int[] nums) {
    // 将数组的第一个元素当作已经排好序的，从第二个元素，即 i 从 1 开始遍历数组
    for (int i = 1, j, current; i < nums.length; i++) {
        // 外围循环开始，把当前 i 指向的值用 current 保存
        current = nums[i];

        // 指针 j 内循环，和 current 值比较，若 j 所指向的值比 current 值大，则该数右移一位
        for (j = i - 1; j >= 0 && nums[j] > current; j--) {
            nums[j + 1] = nums[j];
            }
    
        // 内循环结束，j+1 所指向的位置就是 current 值插入的位置
        nums[j + 1] = current;
    }
}

算法分析

空间复杂度

假设数组的元素个数是n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。

时间复杂度

1. 给定的数组按照顺序已经排好

只需要进行 n-1 次的比较，两两交换次数为0，时间复杂度是O(n)。这是最好的情况。

2. 给定的数组按照逆序排列

在这种情况下，我们需要进行n(n-1)/2次比较，时间复杂度是O(n2)。这是最坏的情况==。==

3. 给定的数组杂乱无章

在这种情况下，平均时间复杂度是 O(n2)。

由此可见，和冒泡排序一样，插入排序的时间复杂度是O(n2)，并且它也是一种稳定的排序算法。

建议：LeetCode 第 147题，要求对一个链表进行插入排序，希望大家去试一试。

归并排序（Merge Sort）

基本思想

核心是==分治==，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。

实现

一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。

排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

代码示例

主体函数的代码实现如下。

void sort(int[] A, int lo, int hi) {
  // 判断是否只剩下最后一个元素
  if (lo >= hi) return;
  
  // 从中间将数组分成两个部分
  int mid = lo + (hi - lo) / 2;
  
  // 分别递归地将左右两半排好序
  sort(A, lo, mid);
  sort(A, mid + 1, hi);

  // 将排好序的左右两半合并  
  merge(A, lo, mid, hi);
}

归并操作的代码实现如下。

void merge(int[] nums, int lo, int mid, int hi) {
    // 复制一份原来的数组,注意，一定要复制！！！如果直接在原数组上操作，会乱序。
    int[] copy = nums.clone();
  
    // 定义一个 k 指针表示从什么位置开始修改原来的数组，i 指针表示左半边的起始位置，j 表示右半边的起始位置
    int k = lo, i = lo, j = mid + 1;
  
    while (k <= hi) {
        if (i > mid) {
            nums[k++] = copy[j++];
        } else if (j > hi) {
          nums[k++] = copy[i++];
        } else if (copy[j] < copy[i]) {
          nums[k++] = copy[j++];
        } else {
          nums[k++] = copy[i++];
        }
    }
}

其中，While 语句比较，一共可能会出现四种情况。

1.左半边的数都处理完毕，只剩下右半边的数，只需要将右半边的数逐个拷贝过去。

2.右半边的数都处理完毕，只剩下左半边的数，只需要将左半边的数逐个拷贝过去就好。

3.右边的数小于左边的数，将右边的数拷贝到合适的位置，j 指针往前移动一位。

4.左边的数小于右边的数，将左边的数拷贝到合适的位置，i 指针往前移动一位。

例题分析

例题：利用归并排序算法对数组 [2, 1, 7, 9, 5, 8] 进行排序。

解题思路

image

首先不断地对数组进行切分，直到各个子数组里只包含一个元素。

接下来递归地按照大小顺序合并切分开的子数组，递归的顺序和二叉树里的前向遍历类似。

1. 合并 [2] 和 [1] 为 [1, 2]。

2. 子数组 [1, 2] 和 [7] 合并。

3. 右边，合并 [9] 和 [5]。

4. 然后合并 [5, 9] 和 [8]。

5. 最后合并 [1, 2, 7] 和 [5, 8, 9][1,2,5,8,9]，就可以把整个数组排好序了。

合并数组 [1, 2, 7] 和 [5, 8, 9] 的操作步骤如下。

image

1.把数组 [1, 2, 7] 用 L 表示，[5, 8, 9] 用 R 表示。

2.合并的时候，开辟分配一个新数组T保存结果，数组大小应该是两个子数组长度的总和

3.然后下标 i、j、k 分别指向每个数组的起始点。

4.接下来，比较下标i和j所指向的元素 L[i] 和 R[j]，按照大小顺序放入到下标 k 指向的地方，1 小于 5。

5.移动 i 和 k，继续比较 L[i] 和 R[j]，2 比 5 小。

6.i 和 k 继续往前移动，5 比 7 小。

7.移动 j 和 k，继续比较 L[i] 和 R[j]，7 比 8 小。

这时候，左边的数组已经处理完毕，直接将右边数组剩余的元素放到结果数组里就好。

合并之所以能成功，先决条件必须是两个子数组都已经分别排好序了。

算法分析

空间复杂度

由于合并 n 个元素需要分配一个大小为n的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。

时间复杂度

归并算法是一个不断递归的过程。

举例： 数组的元素个数是 n，时间复杂度是 T(n) 的函数。

解法： 把这个规模为n的问题分成两个规模分别为n/2的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有n个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。

对于公式求解，不断地把一个规模为n的问题分解成规模为n/2的问题，一直分解到规模大小为 1。如果 n等于2，只需要分一次；如果n等于4，需要分2次。这里的次数是按照规模大小的变化分类的。

以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。

建议： 归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。

快速排序（Quick Sort）

快速排序也采用了分治的思想。

基本思想

快速排序也采用了分治的思想。

实现

把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

举例： 把班里的所有同学按照高矮顺序排成一排。

解法：老师先随机地挑选了同学A，让所有其他同学和A比高矮，比A矮的都站在A的左边，比A高的都站在A的右边。接下来，老师分别从左边和右边的同学里选择了同学 B 和 C，然后不断地筛选和排列下去。

在分成较小和较大的两个子数组过程中，如何选定一个基准值（也就是同学 A、B、C 等）尤为关键。

例题分析

对数组 [2, 1, 7, 9, 5, 8] 进行排序。

解题思路

image

1.按照快速排序的思想，首先把数组筛选成较小和较大的两个子数组。

2.随机从数组里选取一个数作为基准值，比如7，于是原始的数组就被分成了两个子数组。注意：快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出来的时候，原始数组里的排列也被改变了。

3.接下来，在较小的子数组里选 2 作为基准值，在较大的子数组里选 8 作为基准值，继续分割子数组。

4.继续将元素个数大于 1 的子数组进行划分，当所有子数组里的元素个数都为 1 的时候，原始数组也被排好序了。

代码示例

主体函数代码如下。

void sort(int[] nums, int lo, int hi) {
    if (lo >= hi) return; // 判断是否只剩下一个元素，是，则直接返回
    
    // 利用 partition 函数找到一个随机的基准点
    int p = partition(nums, lo, hi);
    
    // 递归地对基准点左半边和右半边的数进行排序
    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

下面用代码实现 partition 函数获得基准值。

int partition(int[] nums, int lo, int hi) {
    // 随机选择一个数作为基准值，nums[hi] 就是基准值,暴力排序是直接选用第一个最为基准值，就会出现特殊情况，造成时间复杂度和冒泡排序一样，为N(n2).随机就尽量减少了这种情况。
    swap(nums, randRange(lo, hi), hi);

    int i, j;

    // 从左到右用每个数和基准值比较，若比基准值小，则放到指针 i 所指向的位置。循环完毕后，i 指针之前的数都比基准值小
    for (i = lo, j = lo; j < hi; j++) {
        if (nums[j] <= nums[hi]) {
            swap(nums, i++, j);
        }
    }

    // 末尾的基准值放置到指针 i 的位置，i 指针之后的数都比基准值大
    swap(nums, i, j);

    // 返回指针 i，作为基准点的位置
    return i;
}

算法分析

时间复杂度

1. 最优情况：被选出来的基准值都是当前子数组的中间数。

这样的分割，能保证对于一个规模大小为n的问题，能被均匀分解成两个规模大小为 n/2 的子问题（归并排序也采用了相同的划分方法），时间复杂度就是：T(n)=2×T(n/2) + O(n)。

把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。

2. 最坏情况：基准值选择了子数组里的最大或者最小值

每次都把子数组分成了两个更小的子数组，其中一个的长度为1，另外一个的长度只比原子数组少 1。

举例： 对于数组来说，每次挑选的基准值分别是 9、8、7、5、2。

解法： 划分过程和冒泡排序的过程类似。

算法复杂度为 O(n2)。

提示：可以通过随机地选取基准值来避免出现最坏的情况。

空间复杂度

和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是 O(logn)。

举例： LeetCode第215题，给定一个尚未排好序的数组，要求找出第k大的数。

解法 1： 直接将数组进行排序，然后得出结果。

解法 2： 快速排序。

每次随机选取一个基准值，将数组分成较小的一半和较大的一半，然后检查这个基准值最后所在的下标是不是 k，算法复杂度只需要 O(n)。

通过LeetCode第215题中可以看出，算法题不会单纯考察一个完整的算法，最优是采用快排思想，而不是全部用快排，然后在去寻找，所以提高算法能力是要理解其思想并能灵活运用。

拓扑排序（Topological Sort）

基本思想

和前面介绍的几种排序不同，拓扑排序应用的场合不再是一个简单的数组，而是研究图论里面顶点和顶点连线之间的性质。拓扑排序就是要将这些顶点按照相连的性质进行排序。

要能实现拓扑排序，得有几个前提：

1.图必须是有向图

2.图里面没有环

拓扑排序一般用来理清具有依赖关系的任务。

举例： 假设有三门课程 A、B、C，如果想要学习课程 C 就必须先把课程 B 学完，要学习课程 B，还得先学习课程 A，所以得出课程的学习顺序应该是 A -> B -> C。

实现

1.将问题用一个有向无环图（DAG,Directed Acyclic Graph）进行抽象表达，定义出哪些是图的顶点，顶点之间如何互相关联。

2.可以利用广度优先搜索或深度优先搜索来进行拓扑排序。

例题分析

有一个学生想要修完 5 门课程的学分，这 5 门课程分别用 1、2、3、4、5 来表示，现在已知学习这些课程有如下的要求：

课程 2 和 4 依赖于课程 1

课程 3 依赖于课程 2 和 4

课程 4 依赖于课程 1 和 2

课程 5 依赖于课程 3 和 4

那么这个学生应该按照怎样的顺序来学习这 5 门课程呢？

解题思路

可以把 5 门课程看成是一个图里的5个顶点，用有向线段按照它们的相互关系连起来，于是得出下面的有向图。

首先可以看到，这个有向图里没有环，无论从哪个顶点出发，都不会再回到那个顶点。并且，这个图里并没有孤岛的出现，因此，我们可以对它进行拓扑排序。

方法就是，一开始的时候，对每个顶点统计它们各自的前驱（也就是入度）：1(0)，2(1)，3(2)，4(1)，5(2)。

image

1.选择其中一个没有前驱（也就是入度为0）的顶点，在这道题里面，顶点1就是我们要找的那个点，将它作为结果输出。同时删除掉该顶点和所有以它作为起始点的有向边，更新顶点的入度表。

2.接下来，顶点 2 就是下一个没有前驱的顶点，输出顶点2，并将以它作为起点的有向边删除，同时更新入度表。

3.再来，顶点 4 成为了没有前驱的顶点，输出顶点 4，删除掉它和顶点 3 和 5 的有向边。

4.然后，顶点 3 没有了前驱，输出它，并删除它与 5 的有向边。

5.最后，顶点 5 没有前驱，输出它，于是得出最后的结果为：1，2，4，3，5。

一般来说，一个有向无环图可以有一个或多个拓扑排序的序列。

代码示例

运用广度优先搜索的方法对这个图的结构进行遍历。在构建这个图的过程中，用一个链接矩阵 adj 来表示这个图的结构，用一个 indegree 的数组统计每个顶点的入度，重点看如何实现拓扑排序。

void sort() {
    Queue<Integer> q = new LinkedList(); // 定义一个队列 q

    // 将所有入度为 0 的顶点加入到队列 q
    for (int v = 0; v < V; v++) {
        if (indegree[v] == 0) q.add(v);
    }

    // 循环，直到队列为空
    while (!q.isEmpty()) {
        int v = q.poll();
        // 每次循环中，从队列中取出顶点，即为按照入度数目排序中最小的那个顶点
        print(v);

        // 将跟这个顶点相连的其他顶点的入度减 1，如果发现那个顶点的入度变成了 0，将其加入到队列的末尾
        for (int u = 0; u < adj[v].length; u++) {
            if (--indegree[u] == 0) {
                q.add(u);
            }
        }
    }
}

算法分析

时间复杂度

统计顶点的入度需要 O(n) 的时间，接下来每个顶点被遍历一次，同样需要 O(n) 的时间，所以拓扑排序的时间复杂度是 O(n)。

建议： 利用深度优先搜索的方法对这道题实现拓扑排序。

结语 这篇复习了面试中经常会被考到的排序算法，最重点内容是归并排序和快速排序。除了要好好理解它们的思路，还必须要能写出没有 bug 的代码，因此建议多做 LeetCode 里面的经典题目。

下一篇将深入讲解递归算法和回溯算法，它们在算法面试中出现的概率是最高的。