排序算法

稳定性：如果待排序元素中 A=B，且排序后 A,B 相对位置不会发生变化，则判定排序算法是稳定的，反之则是不稳定。

内部排序：指的是待排序记录存放在计算机自身的存储器中进行排序的过程。

外部排序：指的是由于待排序记录数量很大，以致于内存无法一次全部容纳所有记录，在排序过程中需要从外存中访问记录的排序过程。

基数排序

基数排序：一种整数排序算法，相当于多趟计数排序，适合位数有限的整数排序。

• 时间复杂度：$O(d(n+r))$
• 辅助空间复杂度：$O(n+r)$

（$d$ 是数字位数，$n$ 是数字个数，$r$ 是基数）

• 稳定排序

void radix_sort(int d, int r){
    int radix = 1;
    for(int i = 1; i <= d; i++){
        for(int j = 0; j < r; j++) s[j] = 0;
        for(int j = 0; j < n; j++) s[a[j] / radix % r]++;
        for(int j = 1; j < r; j++) s[j] += s[j - 1];
        for(int j = n; j >= 0; j--) res[--s[a[j]] / radix % r] = a[j];
        for(int j = 0; j < n; j++) a[j] = res[j];
        radix *= r;
    }
}

希尔排序

希尔排序：实质上是一种分组插入方法，它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

• 时间复杂度：$O(n^{1.3})$
• 辅助空间复杂度：$O(1)$
• 不稳定排序

void shell_sort(){
    for(int d = n / 3; d; d = (d == 2 ? 1 : d / 3)){
        for(int st = 0; st < d; st++){
            for(int i = st + d; i < n; i += d){
                int t = a[i], j = i;
                while(j > st && a[j - d] > t){
                    a[j] = a[j - d];
                    j -= d;
                }
                a[j] = t;
            }
        }
    }
}

二叉树排序

左子树上所有结点的值都小于根结点的值，右子树上所有结点的值都大小根结点的值；对二叉排序树做中序遍历，即为有序序列。

时间复杂度 $O(nlogn)$，辅助空间复杂度 $O(n)$，稳定排序。

堆排序

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端，反复执行此过程，直到序列有序。

• 时间复杂度 $O(nlogn)$
• 辅助空间复杂度 $O(1)$
• 不稳定排序

拓扑排序

拓扑排序是一个有向无环图（DAG Directed acyclic graph）的所有顶点的线性序列。

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑排序不一定是唯一的！

• 1 2 3 4 5
• 1 3 2 4 5

哈夫曼编码

哈夫曼编码（Huffman Coding）是一种可变长编码方式，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，比起定长编码的 ASCII 编码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的；它也是一种用于无损数据压缩的熵编码算法，通常用于压缩重复率比较高的字符数据。

什么是哈夫曼树？

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

结点路径：

将树中一个结点到另一个结点所经历的分支，称为结点路径，比如上图中结点 A 到结点 E 的路径为 A-B-E。

路径长度：

将路径上的分支总数称为路径长度，比如上图中结点 A 到结点 E 的路径长度为 2。

结点的带权路径长度：

结点的带权路径长度=从根结点到某结点的路径长度*结点权值(w)。

比如上图中结点 A 到结点 D 的路径长度为 2，权值为 8，则带权路径长度为 2∗8=16。

树的带权路径长度(WPL)：

将树中所有叶子结点的带权路径长度加和，称为树的带权路径长度。比如上图中，三个叶子结点 C、D、E，对应的路径长度分别为 1、2、2，对应的权值分别为 4、8、3，则树的带权路径长度为： 1∗4+2∗8+2∗3=26。即：

$WPL=l_1∗w_1 + l_2∗w_2+…+ l_n∗w_n$

其中了表示路径长度，w 表示权值，n 表示叶子结点个数。

哈夫曼编码算法步骤

第一步：我们需要先计算字符串中每个字符出现的频率：

第二步：按照字符出现的频率进行排序，组成一个队列 Q。出现频率最低的在前面，出现频率高的在后面。

第三步：把这些字符作为叶子结点开始构建一颗哈夫曼树。

（1）首先创建一个空结点 z，将最小频率的字符分配给 z 的左侧，并将频率排在第二位的分配给 z 的右侧，然后将 z 赋值为两个字符频率的和；然后从队列 Q 中删除 B 和 D，并将它们的和添加到队列中，上图中 * 表示的位置。

（2）紧接着，重新创建一个空的结点 z，并将 4 作为左侧的结点，频率为 5 的 A 作为右侧的结点，4 与 5 的和作为父结点，并把这个和按序加入到队列中，再根据频率从小到大构建树结构（小的在左）。

（3）继续按照之前的思路构建树，直到所有的字符都出现在树的结点中，哈弗曼树构建完成。结点的带权路径长度为从根结点到该结点的路径长度与结点权值的乘积。该二叉树的带权路径长度

WPL = 6 ∗ 1 + 5 ∗ 2 + 3 ∗ 3 + 1 ∗ 3 = 28

第四步：对字符进行编码

哈夫曼树构建完成，下面我们要对各个字母进行编码，编码原则是：对于每个非叶子结点，将 0 分配给连接线的左侧，1 分配给连接线的右侧，最终得到字符的编码就是从根结点开始，到该结点的路径上的 0 1 序列组合。

在没有经过哈夫曼编码之前，字符串 BCAADDDCCACACAC 的二进制为：10000100100001101000001010000010100010001000100010001000100001101000011010000010100001101000001010000110100000101000011 占了 120 Bit。

编码之后为只占了 28 比特：1000111110110110100110110110

从本质上讲，哈夫曼编码是将最宝贵的资源（最短的编码）给出现概率最多的数据（贪心）。

哈夫曼树和编码都不唯一！只有树的WPL(带权路径长度)才是唯一的！

哈夫曼编码有两个特点：

1. 带权路径长度 WPL 最短且唯一；
2. 编码互不为前缀（一个编码不是另一个编码的开头）。

• 为什么通过哈夫曼编码后得到的二进制码不会有前缀的问题呢？

这是因为在哈夫曼树中，每个字母对应的结点都是叶子结点，而他们对应的二进制码是由根结点到各自结点的路径所决定的，正因为是叶子结点，每个结点的路径不可能和其他结点有前缀的关系。

• 为什么通过哈夫曼编码获得的二进制码短呢？

因为哈夫曼树是带权路径长度最短的树，权值较大的结点离根结点较近。而带权路径长度是指：树中所有的叶子结点的权值乘上其到根结点的路径长度，这与最终的哈夫曼编码总长度成正比关系的。

随堂检测

1.将数组 {8，23，4，16，77，-5，53，100} 中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（ ）次。

{{ select(1) }}

• 4
• 5
• 6
• 7

2.（ ）的平均时间复杂度为 O(nlogn)，其中 n 是待排序的元素个数。

{{ select(2) }}

• 快速排序
• 插入排序
• 冒泡排序
• 基数排序

3.在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（ ）。

{{ select(3) }}

• 堆排序
• 桶排序
• 冒泡排序
• 快速排序

4.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（ ）。

{{ select(4) }}

• 选择排序
• 冒泡排序
• 插入排序
• 基数排序

5.递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。

{{ select(5) }}

• 队列
• 多维数组
• 线性表
• 栈

6.在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是（ ）。

{{ select(6) }}

• 希尔排序
• 冒泡排序
• 插入排序
• 选择排序

7.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的（ ）。

{{ select(7) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

8.体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。

{{ select(8) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

9.使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5,4,3,2,1 需要执行（ ）次操作，才能完成冒泡排序。

{{ select(9) }}

• 0
• 5
• 10
• 15

10.排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列排序算法稳定的是（ ）。

{{ select(10) }}

• 选择排序
• 冒泡排序
• 快速排序
• 希尔排序

11.对于给定的序列 $\{a_1,a_2…a_i…a_j…a_k\}$，我们把 $(i,j)$ 称为逆序对当且仅当 $i<j$ 且 $a_i>a_j$。那么序列 $\{1,7,2,3,5,4\}$ 的逆序对数为（ ）个？。

{{ select(11) }}

• 4
• 5
• 6
• 7

12.对于给定的序列 {7,5,1,9,3,6,8,4}，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 3 ？（ ）。

注：我们把 $(i,j)$ 称为逆序对当且仅当 $i<j$ 且 $a_i>a_j$。

{{ select(12) }}

• 7
• 5
• 3
• 8

13.基于比较的排序时间复杂度的下限是（ ），其中n表示待排序的元素个数。

{{ select(13) }}

• $O(n)$
• $O(nlogn)$
• $O(logn)$
• $O(n^2)$

14.考虑如下递归算法：

int solve(n)  
    if n<=1 return 1  
    else if n>=5 return n*solve(n-2)  
    else return n*solve(n-1)

则调用 solve(7) 得到的返回结果为（ ）。

{{ select(14) }}

• 105
• 840
• 210
• 420

15.在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

{{ select(15) }}

• 系统分配的栈空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出
• 系统分配的堆空间溢出

16.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、200。那么，“也”字的编码长度是（ ）。

{{ select(16) }}

• 1
• 2
• 3
• 4

17.在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

{{ select(17) }}

• 枚举
• 贪心
• 递归
• 动态规划

18.（ ）就是把一个复杂的问题分成两个或者更多的相同或相似的子问题，再把子问题分成更小的子问题，…，直到最后的子问题可以简单的直接求解。而原问题的解就是子问题解的并。

{{ select(18) }}

• 动态规划
• 贪心
• 分治
• 搜索

19.设有100个数据元素，采用折半搜索时，最大的比较次数为（ ）。

{{ select(19) }}

• 6
• 7
• 8
• 10

20.快速排序最坏情况下的算法时间复杂度为（ ）？

{{ select(20) }}

• $O(logn)$
• $O(n)$
• $O(nlogn)$
• $O(n^2)$