数据结构-借假修真-高级数据结构

1. 基本的排序算法

• 冒泡排序（Bubble Sort）

• 插入排序（Insertion Sort）

2. 常考的排序算法

• 归并排序（Merge Sort）

• 快速排序（Quick Sort）

• 拓扑排序（Topological Sort）

3. 其他排序算法

• 堆排序（Heap Sort）

• 桶排序（Bucket Sort)

冒泡排序 (Bubble Sort)

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

• 算法分析

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

  • 时间复杂度

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

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

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

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

    3. 给定的数组杂乱无章

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

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

插入排序（Insertion Sort）

• 基本思想

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

• 特点：

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

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

• 时间复杂度

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

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

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

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

3. 给定的数组杂乱无章

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

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

归并排序（Merge Sort）

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

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

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

算法分析
空间复杂度
由于合并 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)。

时间复杂度

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)。

快速排序（Quick Sort）

基本思想

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

实现

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

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

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

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

算法分析
时间复杂度

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)。

拓扑排序（Topological Sort）

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

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

• 图必须是有向图

• 图里面没有环

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

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

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

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

• 例题分析
  有一个学生想要修完 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(2)，5(2)。

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

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

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

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

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

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

算法分析
时间复杂度

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

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