常见排序算法分析

博主： wmicheng
发布时间：2025 年 02 月 11 日
44 次浏览
暂无评论
13213字数
分类：数据结构

## 排序基本概念

> #### 定义

- `排序`（`Sort`），就是重新排列表中的元素，使表中的元素满足`按关键字有序`的过程。
- 输入：n个记录$R_1, R_2,…, R_n$，对应的关键字为$k_1, k_2,…, k_n$。
- 输出：输入序列的一个重排$R_1ʹ, R_2ʹ,…, R_nʹ$，使得有$k_1ʹ≤k_2ʹ≤…≤k_nʹ$（也可递减）

![排序概念](https://wmicheng.top/images/note/img_Search_Sort/排序概念.png)

**排序算法的评价指标：**

- 时间复杂度
- 空间复杂度
- 算法的稳定性

![排序概念1](https://wmicheng.top/images/note/img_Search_Sort/排序概念1.png)

**排序算法的分类：**

- 内部排序：数据都在内存中，`关注如何使算法时、空复杂度更低`
- 外部排序：数据太多，无法全部放入内存，`还要关注如何使读/写磁盘次数更少`

![排序概念2](https://wmicheng.top/images/note/img_Search_Sort/排序概念2.png)

![排序概念3](https://wmicheng.top/images/note/img_Search_Sort/排序概念3.png)

**https://www.cs.usfca.edu/%7Egalles/visualization/Algorithms.html**

## 插入排序

> #### 算法思想

![insertionSort](https://wmicheng.top/images/note/img_Search_Sort/insertionSort.gif)

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

> #### 代码实现

| 不带哨兵                                                     | 带哨兵                                                       |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![插入排序](https://wmicheng.top/images/note/img_Search_Sort/插入排序.png) | ![插入排序1](https://wmicheng.top/images/note/img_Search_Sort/插入排序1.png) |

**算法效率分析：**

- **空间复杂度**：$O(1)$
- **时间复杂度**：主要来自对比关键字、移动元素，若有 n 个元素，则需要 n-1 趟处理
  
  - 最好时间复杂度：$O(n)$ 共n-1趟处理，每一趟只需要对比关键字1次，不用移动元素
  - 最坏时间复杂度：$O(n^2)$ 共n-1趟处理，每一趟都需要从尾移到到头（全部逆序）
- **算法稳定性**：`稳定`

> #### 优化——折半插入排序

**思路**

- 先用折半查找找到应该插入的位置，再移动元素
- 当 low>high 时折半查找停止，应将 \[low, i-1\] 内的元素全部右移，并将 A\[0\] 复制到 low 所指位置
- 当 A\[mid\]==A\[0\] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置

**代码实现**

![插入排序2](https://wmicheng.top/images/note/img_Search_Sort/插入排序2.png)

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是$O(n^2)$

> #### 对链表进行插入排序

- 使用链表不需要对序列进行依次友谊，移动元素的次数变少了
- 但是关键字对比的次数依然是$O(n^2)$ 数量级，整体来看时间复杂度依然是$O(n^2)$

![插入排序3](https://wmicheng.top/images/note/img_Search_Sort/插入排序3.png)

## 希尔排序

> #### 算法思想

![shellsort](https://wmicheng.top/images/note/img_Search_Sort/shellsort.gif)

- 先追求表中元素部分有序，再逐渐逼近全局有序
- 先将待排序表分割成若干形如 $L[i, i + d, i + 2d,…, i + kd]$ 的“特殊”子表，对各个子表分别进行直接插入排序。缩小`增量d`，重复上述过程，直到d=1为止。

![希尔排序3](https://wmicheng.top/images/note/img_Search_Sort/希尔排序3.png)

> #### 代码实现

![希尔排序2](https://wmicheng.top/images/note/img_Search_Sort/希尔排序2.png)

> #### 算法性能分析

![希尔排序1](https://wmicheng.top/images/note/img_Search_Sort/希尔排序1.png)

**空间复杂度**：O(1)

**时间复杂度**：

- 和增量序列 $d_1, d_2, d_3…$ 的选择有关，目前无法用数学手段证明确切的时间复杂度
- 最坏时间复杂度为 $O(n^2)$，当n在某个范围内时，可达$O(n^{1.3})$

**稳定性**：`不稳定`

**适用性**：仅适用于顺序表，不适用于链表

## 冒泡排序

> #### 算法思想

![bubbleSort](https://wmicheng.top/images/note/img_Search_Sort/bubbleSort.gif)

- 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A\[i-1\]>A\[i\]），则交换它们，直到序列比较完
- 这样过程称为“`一趟`”冒泡排序
- 第n趟结束后，最小的n个元素会“冒”到最前边
- 若某一趟排序没有发生“交换”，说明此时已经整体有序。
- 可以从后往前冒泡，也可以冲前往后冒泡

> #### 代码实现

![冒泡排序1](https://wmicheng.top/images/note/img_Search_Sort/冒泡排序1.png)

> #### 算法性能分析

- 空间复杂度：$O(1)$
- 时间复杂度：
  
  - 最好情况（有序）：$O(n)$
  - 最坏情况（逆序）：$O(n^2)$
  - 平均情况：$O(n^2)$
- 稳定性：稳定
- 适用性：顺序表、链表都可以

![冒泡排序2](https://wmicheng.top/images/note/img_Search_Sort/冒泡排序2.png)

## 快速排序

> #### 算法思想

![quickSort](https://wmicheng.top/images/note/img_Search_Sort/quickSort.gif)

- 在待排序表L\[1…n\]中任取一个元素pivot作为枢轴（或基准，通常取⾸元素）
- 通过一趟排序将待排序表划分为独立的两部分L\[1…k-1\]和L\[k+1…n\]
- 使得L\[1…k-1\]中的所有元素小于pivot，L\[k+1…n\]中的所有元素大于等于pivot
- 则`pivot`放在了其最终位置L(k)上，这个过程称为一次“`划分`”
- 然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上

> #### 代码实现

![快速排序](https://wmicheng.top/images/note/img_Search_Sort/快速排序.png)

> #### 算法性能分析

![快速排序1](https://wmicheng.top/images/note/img_Search_Sort/快速排序1.png)

**n个结点的二叉树**

- 最小高度$ = ⌊log_2n⌋ + 1$
- 最大高度$ = n$

**时间复杂度**$=O(n*递归层数)$

- `最好`时间复杂度**$=O(nlog_2n)$
  
  - 每次选的枢轴元素都能将序列划分成均匀的两部分
- `最坏`时间复杂度**$=O(n^2)$
- 若序列原本就有序或逆序，则时、空复杂度最高（可优化，尽量选择可以把数据中分的枢轴元素。）

**空间复杂度**=O(递归层数)

- 最好空间复杂度$=O(log_2n)$
- 最坏空间复杂度$=O(n)$

若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

若初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）

**快速排序算法优化思路**：尽量选择可以把数据中分的枢轴元素。

- 选头、中、尾三个位置的元素，取中间值作为枢轴元素；
- 随机选一个元素作为枢轴元素

快速排序是所有内部排序算法中平均性能最优的排序算法

**稳定性：`不稳定`

![快速排序2](https://wmicheng.top/images/note/img_Search_Sort/快速排序2.png)

## 简单选择排序

> #### 算法思想

每一趟在待排序元素中选取关键字最小（或最大）的元素（每一趟待排序序列长度-1）加入有序子序列（每一趟有序序列长度+1）

![selectionSort](https://wmicheng.top/images/note/img_Search_Sort/selectionSort.gif)

> #### 代码实现

![简单选择排序](https://wmicheng.top/images/note/img_Search_Sort/简单选择排序.png)

> #### 算法性能分析

- 无论有序、逆序、还是乱序，一定需要 $n-1$ 趟处理
- 总共需要对比关键字$(n-1)+(n-2)+\ldots+1=\frac{n(n-1)}{2}$次
- 元素交换次数 $< n-1$
- 空间复杂度：$O(1)$
- 时间复杂度$=O(n^2)$
- 稳定性：不稳定
- 适用性：既可以用于顺序表，也可用于链表

![简单选择排序1](https://wmicheng.top/images/note/img_Search_Sort/简单选择排序1.png)

## 堆排序

![heapSort](https://wmicheng.top/images/note/img_Search_Sort/heapSort.gif)

![堆排序1](https://wmicheng.top/images/note/img_Search_Sort/堆排序1.png)

> #### 堆的定义

若n个关键字序列L\[1…n\] 满足下面某一条性质，则称为`堆（Heap）`：

- 若满足：$L(i)≥L(2i)$且$L(i)≥L(2i+1) $$(1 ≤ i ≤n/2 )$则为`大根堆（大顶堆`）
  
  - 即完全二叉树中，任意根≥左、右
- 若满足：$L(i)≤L(2i)$且$L(i)≤L(2i+1)$ $(1 ≤ i ≤n/2 )$则为`小根堆（小顶堆）`
  
  - 即完全二叉树中，任意根≤左、右

![堆排序](https://wmicheng.top/images/note/img_Search_Sort/堆排序.png)

> #### 建立大根堆

**把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整**

- 在顺序存储的完全二叉树中，非终端结点编号 i≤⌊n/2⌋
- 检查当前结点是否满足：`根`$≥$`左、右`，`若不满足，将当前结点与更大的一个孩子互换`
  
  - i的左孩子：$2i$
  - i的右孩子：$2i+1$
  - i的父结点：$[i/2]$
- 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）

建立大根堆（代码）：

![堆排序3](https://wmicheng.top/images/note/img_Search_Sort/堆排序3.png)

> #### 基于大根堆进行排序

选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列

堆排序每一趟完成以下工作：

- 将堆顶元素（就是最大的元素）加入有序子序列（与待排序序列中的最后一个元素交换）
- 并将`待排序元素序列`再次调整为大根堆（小元素不断“下坠”）

`注意：大根堆获得的排序序列是递增序列，小跟堆相反，获得的是递减序列`

> #### 代码实现（大根堆排序）

> #### 堆排序的效率分析

- 建堆的过程，关键字对比次数不超过4n，建堆时间复杂度=O(n)
- 堆排序的时间复杂度 $=O(n) + O(nlog_2n) = O(nlog_2n)$
- 堆排序的空间复杂度 $=O(1)$
- 稳定性：不稳定

![堆排序2](https://wmicheng.top/images/note/img_Search_Sort/堆排序2.png)

### 堆的插入删除

> #### 基本操作

- i的左孩子：2i
- i的右孩子：2i+1
- i的父结点：[i/2]

> #### 在堆中插入新元素

- 对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。
- 新元素就这样一路“上升”，直到无法继续上升为止

> #### 在堆中删除元素

- 被删除的元素用堆底元素替代
- 然后让该元素不断“下坠”，直到无法下坠为止

> #### 关键字对比次数

- 每次“上升”调整只需对比关键字1次
- 每次“下坠”调整可能需要对比关键字2次，也可能只需对比1次

![堆排序5](https://wmicheng.top/images/note/img_Search_Sort/堆排序5.png)

## 归并排序

> #### 算法思想

![mergeSort](https://wmicheng.top/images/note/img_Search_Sort/mergeSort.gif)

![堆排序9](https://wmicheng.top/images/note/img_Search_Sort/堆排序9.png)

- 把两个或多个已经有序的序列合并成一个
- 对于两个有序序列，将i、j指针指向序列的表头，选择更小的一个放入k所指的位置
- k++，i/j指向更小元素的指针++
- 只剩一个子表未合并时，可以将该表的剩余元素全部加到总表
- m路归并：每选出一个小的元素，需要对比关键字m-1次
- 核心操作：把数组内的两个有序序列归并为一个

> #### 代码实现

![堆排序8](https://wmicheng.top/images/note/img_Search_Sort/堆排序8.png)

- low是数组中第一个有序序列的开始
- mid是数组中第一个有序序列的结尾
- high是数组中第二个有序序列的结尾
- 辅助数组B临时存放这两段有序序列

**算法效率分析：**

- 2路归并的“归并树”形态上就是一棵倒立的二叉树
- 二叉树的第h层最多有$2 ^ {h-1}$个结点，若树高为h，则应满足$n <= 2 ^ {h-1}$，即$h − 1 = ⌈log_2n⌉$
- n个元素进行2路归并排序，归并趟数$=⌈log_2n⌉$
- 每趟归并时间复杂度为$O(n)$，则算法时间复杂度$O(nlog_2n)$
- 空间复杂度$=O(n)$，来自于辅助数组B
- 稳定性：稳定

## 基数排序

> #### 算法思想

![radixSort](https://wmicheng.top/images/note/img_Search_Sort/radixSort.gif)

![基数排序3](https://wmicheng.top/images/note/img_Search_Sort/基数排序3.png)

基数排序得到`递增`序列的过程如下：

- 初始化： 设置 r 个空队列，$Q_0, Q_1,…, Q_{r−1}$
- 按照各个 关键字位 权重递增的次序（个、十、百），对 d 个关键字位分别做“分配”和“收集”
- 分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入 $Q_x$ 队尾
- 收集：把 $Q_0, Q_1,…, Q_{r−1}$ 各个队列中的结点依次出队并链接

![基数排序2](https://wmicheng.top/images/note/img_Search_Sort/基数排序2.png)

![基数排序1](https://wmicheng.top/images/note/img_Search_Sort/基数排序1.png)

> #### 算法效率分析

![基数排序4](https://wmicheng.top/images/note/img_Search_Sort/基数排序4.png)

- 稳定性：稳定

> #### 基数排序的应用

![基数排序5](https://wmicheng.top/images/note/img_Search_Sort/基数排序5.png)

**基数排序擅长解决的问题**：

- 数据元素的关键字可以方便地拆分为 d 组，且 d 较小
- 每组关键字的取值范围不大，即 r 较小
- 数据元素个数 n 较大

![基数排序6](https://wmicheng.top/images/note/img_Search_Sort/基数排序6.png)

## 外部排序

> #### 外存、内存的数据交换

**外存**：

- 操作系统以“块”为单位对磁盘存储空间进行管理
- 如：每块大小1KB各个磁盘块内存放着各种各样的数据

**内存**：

- 磁盘的读/写以“`块`”为单位
- 数据读入内存后才能被修改
- 修改完了还要写回磁盘

![外部排序1](https://wmicheng.top/images/note/img_Search_Sort/外部排序1.png)

> #### 外部排序原理

- 数据元素太多，无法一次全部读入内存进行排序
- 使用“归并排序”的方法，最少只需在内存或只能怪分配3块大小的缓冲区即可对任意一个大文件进行排序
- ”归并排序“要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘

**构造初始“归并段”**：

![外部排序1](https://wmicheng.top/images/note/img_Search_Sort/外部排序1.png)

若有N个记录，内存工作区可以容纳L个记录，则初始归并段数量=r=N/L

**第一趟归并**：

![外部排序3](https://wmicheng.top/images/note/img_Search_Sort/外部排序3.png)

**第二趟归并**：

![外部排序4](https://wmicheng.top/images/note/img_Search_Sort/外部排序4.png)

**第三趟归并**：

![外部排序5](https://wmicheng.top/images/note/img_Search_Sort/外部排序5.png)

> #### 时间开销分析

![外部排序6](https://wmicheng.top/images/note/img_Search_Sort/外部排序6.png)

`外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间`

> #### 优化思路

`多路归并`

![外部排序7](https://wmicheng.top/images/note/img_Search_Sort/外部排序7.png )

`采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数`（`重要结论`）

![外部排序7](https://wmicheng.top/images/note/img_Search_Sort/外部排序7.png)

**多路归并带来的负面影响**：

- `k`路归并时，需要开辟`k`个输入缓冲区，内存开销增加
- 每挑选一个关键字需要对比关键字（`k-1`）次，内部归并所需时间增加（**可使用败者树优化**）

`减少初始归并段数量`

![外部排序9](https://wmicheng.top/images/note/img_Search_Sort/外部排序9.png)

- 生成初始归并段的“内存工作区”越大，初始归并段越长

![外部排序10](https://wmicheng.top/images/note/img_Search_Sort/外部排序10.png)

## 败者树

> #### 问题引入（多路平衡带来的问题）

![败者树1](https://wmicheng.top/images/note/img_Search_Sort/败者树1.png)

> #### 定义

- 可视为一棵完全二叉树（多了一个头头）
- k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。
- 即失败者留在这一回合，胜利者进入下一回合比拼

![败者树2](https://wmicheng.top/images/note/img_Search_Sort/败者树2.png)

> #### 败者树在多路平衡归并中的应用

|                                                              |                                                              |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![败者树3](https://wmicheng.top/images/note/img_Search_Sort/败者树3.png) | ![败者树4](https://wmicheng.top/images/note/img_Search_Sort/败者树4.png) |

> #### 败者树的存储结构

![败者树5](https://wmicheng.top/images/note/img_Search_Sort/败者树5.png)

**对于k路归并，第一次构造败者树需要对比关键字$k-1$次**

有了败者树，选出最小元素，只需对比关键字$[log_2k]$次

## 置换-选择排序

![败者树6](https://wmicheng.top/images/note/img_Search_Sort/败者树6.png)

使用置换-选择排序，可以让每个初始归并段的长度超过内存工作区大小的限制

![置换选择排序](https://wmicheng.top/images/note/img_Search_Sort/置换选择排序.png)

![置换选择排序1](https://wmicheng.top/images/note/img_Search_Sort/置换选择排序1.png)

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。

> #### 置换-选择算法的步骤如下

1. 从FI输入w个记录到工作区WA。
2. 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
3. 将MINIMAX记录输出到FO中去。
4. 若FI不空，则从FI输入下一个记录到WA中。
5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
6. 重复3.～5.，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
7. 重复2.～6.，直至WA为空。由此得到全部初始归并段。

## 最佳归并树

| 归并树神秘性质                                               |                                                              |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![最佳归并树](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树.png) | ![最佳归并树1](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树1.png) |

- 归并过程中`磁盘I/O次数=归并树的WPL*2`（`重要结论`）
- **因此要让磁盘I/O次数最小，就要使归并树的WPL最小即构建一个`哈夫曼树`

> #### m叉最佳归并树的构造

| 2路归并最佳归并树                                            | 3路归并最佳归并树                                            |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![最佳归并树2](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树2.png) | ![最佳归并树3](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树3.png) |

![最佳归并树5](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树5.png)

- 注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树
- 则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造

![最佳归并树4](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树4.png)

> 增加虚段的数量

![最佳归并树6](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树6.png)

![最佳归并树7](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树7.png)

## 总结

| 排序方法         | 时间复杂度(`平均`) | 时间复杂度(`最坏`) | 时间复杂度(`最好`) | `空间`复杂度 | 稳定性   |
| ---------------- | ------------------ | ------------------ | ------------------ | ------------ | -------- |
| **直接插入排序** | $O(n^2)$           | $O(n^2)$           | $O(n)$             | $O(1)$       | `稳定`   |
| **折半插人排序** | $O(nlog_2n)$       | $O(n^2)$           | $O(n^2)$           | $O(1)$       | `稳定`   |
| **希尔排序**     | $O(n^{1.3})$       | $O(n)$             | $O(n)$             | $O(1)$       | `不稳定` |
| **选择排序**     | $O(n^2)$           | $O(n^2)$           | $O(n^2)$           | $O(1)$       | `不稳定` |
| **冒泡排序**     | $O(n^2)$           | $O(n)$             | $O(n)$             | $O(1)$       | `稳定`   |
| **快速排序**     | $O(nlog_2n)$       | $O(n^2)$           | $O(nlog_2n)$       | $O(nlog_2n)$ | `不稳定` |
| **堆排序**       | $O(nlog_2n)$       | $O(nlog_2n)$       | $O(nlog_2n)$       | $O(1)$       | `不稳定` |
| **归并排序**     | $O(nlog_2n)$       | $O(nlog_2n)$       | $O(nlog_2n)$       | $O(n)$       | `稳定`   |
| **基数排序**     | $O(d(n + rd))$     | $O(d(n + rd))$     | $O(d(n+ rd))$      | $O(n + rd)$  | `稳定`   |

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

常见排序算法分析

wmicheng • 2025 年 02 月 11 日

## 排序基本概念

> #### 定义

![排序概念](https://wmicheng.top/images/note/img_Search_Sort/排序概念.png)

**排序算法的评价指标：**

- 时间复杂度
- 空间复杂度
- 算法的稳定性

![排序概念1](https://wmicheng.top/images/note/img_Search_Sort/排序概念1.png)

**排序算法的分类：**

- 内部排序：数据都在内存中，`关注如何使算法时、空复杂度更低`
- 外部排序：数据太多，无法全部放入内存，`还要关注如何使读/写磁盘次数更少`

![排序概念2](https://wmicheng.top/images/note/img_Search_Sort/排序概念2.png)

![排序概念3](https://wmicheng.top/images/note/img_Search_Sort/排序概念3.png)

**https://www.cs.usfca.edu/%7Egalles/visualization/Algorithms.html**

## 插入排序

> #### 算法思想

![insertionSort](https://wmicheng.top/images/note/img_Search_Sort/insertionSort.gif)

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

> #### 代码实现

**算法效率分析：**

> #### 优化——折半插入排序

**思路**

**代码实现**

![插入排序2](https://wmicheng.top/images/note/img_Search_Sort/插入排序2.png)

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是$O(n^2)$

> #### 对链表进行插入排序

- 使用链表不需要对序列进行依次友谊，移动元素的次数变少了
- 但是关键字对比的次数依然是$O(n^2)$ 数量级，整体来看时间复杂度依然是$O(n^2)$

![插入排序3](https://wmicheng.top/images/note/img_Search_Sort/插入排序3.png)

## 希尔排序

> #### 算法思想

![shellsort](https://wmicheng.top/images/note/img_Search_Sort/shellsort.gif)

![希尔排序3](https://wmicheng.top/images/note/img_Search_Sort/希尔排序3.png)

> #### 代码实现

![希尔排序2](https://wmicheng.top/images/note/img_Search_Sort/希尔排序2.png)

> #### 算法性能分析

![希尔排序1](https://wmicheng.top/images/note/img_Search_Sort/希尔排序1.png)

**空间复杂度**：O(1)

**时间复杂度**：

- 和增量序列 $d_1, d_2, d_3…$ 的选择有关，目前无法用数学手段证明确切的时间复杂度
- 最坏时间复杂度为 $O(n^2)$，当n在某个范围内时，可达$O(n^{1.3})$

**稳定性**：`不稳定`

**适用性**：仅适用于顺序表，不适用于链表

## 冒泡排序

> #### 算法思想

![bubbleSort](https://wmicheng.top/images/note/img_Search_Sort/bubbleSort.gif)

> #### 代码实现

![冒泡排序1](https://wmicheng.top/images/note/img_Search_Sort/冒泡排序1.png)

> #### 算法性能分析

![冒泡排序2](https://wmicheng.top/images/note/img_Search_Sort/冒泡排序2.png)

## 快速排序

> #### 算法思想

![quickSort](https://wmicheng.top/images/note/img_Search_Sort/quickSort.gif)

> #### 代码实现

![快速排序](https://wmicheng.top/images/note/img_Search_Sort/快速排序.png)

> #### 算法性能分析

![快速排序1](https://wmicheng.top/images/note/img_Search_Sort/快速排序1.png)

**n个结点的二叉树**

- 最小高度$ = ⌊log_2n⌋ + 1$
- 最大高度$ = n$

**时间复杂度**$=O(n*递归层数)$

**空间复杂度**=O(递归层数)

- 最好空间复杂度$=O(log_2n)$
- 最坏空间复杂度$=O(n)$

若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

若初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）

**快速排序算法优化思路**：尽量选择可以把数据中分的枢轴元素。

- 选头、中、尾三个位置的元素，取中间值作为枢轴元素；
- 随机选一个元素作为枢轴元素

快速排序是所有内部排序算法中平均性能最优的排序算法

**稳定性：`不稳定`

![快速排序2](https://wmicheng.top/images/note/img_Search_Sort/快速排序2.png)

## 简单选择排序

> #### 算法思想

每一趟在待排序元素中选取关键字最小（或最大）的元素（每一趟待排序序列长度-1）加入有序子序列（每一趟有序序列长度+1）

![selectionSort](https://wmicheng.top/images/note/img_Search_Sort/selectionSort.gif)

> #### 代码实现

![简单选择排序](https://wmicheng.top/images/note/img_Search_Sort/简单选择排序.png)

> #### 算法性能分析

![简单选择排序1](https://wmicheng.top/images/note/img_Search_Sort/简单选择排序1.png)

## 堆排序

![heapSort](https://wmicheng.top/images/note/img_Search_Sort/heapSort.gif)

![堆排序1](https://wmicheng.top/images/note/img_Search_Sort/堆排序1.png)

> #### 堆的定义

若n个关键字序列L\[1…n\] 满足下面某一条性质，则称为`堆（Heap）`：

![堆排序](https://wmicheng.top/images/note/img_Search_Sort/堆排序.png)

> #### 建立大根堆

**把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整**

建立大根堆（代码）：

![堆排序3](https://wmicheng.top/images/note/img_Search_Sort/堆排序3.png)

> #### 基于大根堆进行排序

选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列

堆排序每一趟完成以下工作：

`注意：大根堆获得的排序序列是递增序列，小跟堆相反，获得的是递减序列`

> #### 代码实现（大根堆排序）

> #### 堆排序的效率分析

![堆排序2](https://wmicheng.top/images/note/img_Search_Sort/堆排序2.png)

### 堆的插入删除

> #### 基本操作

- i的左孩子：2i
- i的右孩子：2i+1
- i的父结点：[i/2]

> #### 在堆中插入新元素

- 对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。
- 新元素就这样一路“上升”，直到无法继续上升为止

> #### 在堆中删除元素

- 被删除的元素用堆底元素替代
- 然后让该元素不断“下坠”，直到无法下坠为止

> #### 关键字对比次数

- 每次“上升”调整只需对比关键字1次
- 每次“下坠”调整可能需要对比关键字2次，也可能只需对比1次

![堆排序5](https://wmicheng.top/images/note/img_Search_Sort/堆排序5.png)

## 归并排序

> #### 算法思想

![mergeSort](https://wmicheng.top/images/note/img_Search_Sort/mergeSort.gif)

![堆排序9](https://wmicheng.top/images/note/img_Search_Sort/堆排序9.png)

> #### 代码实现

![堆排序8](https://wmicheng.top/images/note/img_Search_Sort/堆排序8.png)

- low是数组中第一个有序序列的开始
- mid是数组中第一个有序序列的结尾
- high是数组中第二个有序序列的结尾
- 辅助数组B临时存放这两段有序序列

**算法效率分析：**

## 基数排序

> #### 算法思想

![radixSort](https://wmicheng.top/images/note/img_Search_Sort/radixSort.gif)

![基数排序3](https://wmicheng.top/images/note/img_Search_Sort/基数排序3.png)

基数排序得到`递增`序列的过程如下：

![基数排序2](https://wmicheng.top/images/note/img_Search_Sort/基数排序2.png)

![基数排序1](https://wmicheng.top/images/note/img_Search_Sort/基数排序1.png)

> #### 算法效率分析

![基数排序4](https://wmicheng.top/images/note/img_Search_Sort/基数排序4.png)

- 稳定性：稳定

> #### 基数排序的应用

![基数排序5](https://wmicheng.top/images/note/img_Search_Sort/基数排序5.png)

**基数排序擅长解决的问题**：

- 数据元素的关键字可以方便地拆分为 d 组，且 d 较小
- 每组关键字的取值范围不大，即 r 较小
- 数据元素个数 n 较大

![基数排序6](https://wmicheng.top/images/note/img_Search_Sort/基数排序6.png)

## 外部排序

> #### 外存、内存的数据交换

**外存**：

- 操作系统以“块”为单位对磁盘存储空间进行管理
- 如：每块大小1KB各个磁盘块内存放着各种各样的数据

**内存**：

- 磁盘的读/写以“`块`”为单位
- 数据读入内存后才能被修改
- 修改完了还要写回磁盘

![外部排序1](https://wmicheng.top/images/note/img_Search_Sort/外部排序1.png)

> #### 外部排序原理

**构造初始“归并段”**：

![外部排序1](https://wmicheng.top/images/note/img_Search_Sort/外部排序1.png)

若有N个记录，内存工作区可以容纳L个记录，则初始归并段数量=r=N/L

**第一趟归并**：

![外部排序3](https://wmicheng.top/images/note/img_Search_Sort/外部排序3.png)

**第二趟归并**：

![外部排序4](https://wmicheng.top/images/note/img_Search_Sort/外部排序4.png)

**第三趟归并**：

![外部排序5](https://wmicheng.top/images/note/img_Search_Sort/外部排序5.png)

> #### 时间开销分析

![外部排序6](https://wmicheng.top/images/note/img_Search_Sort/外部排序6.png)

`外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间`

> #### 优化思路

`多路归并`

![外部排序7](https://wmicheng.top/images/note/img_Search_Sort/外部排序7.png )

`采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数`（`重要结论`）

![外部排序7](https://wmicheng.top/images/note/img_Search_Sort/外部排序7.png)

**多路归并带来的负面影响**：

`减少初始归并段数量`

![外部排序9](https://wmicheng.top/images/note/img_Search_Sort/外部排序9.png)

- 生成初始归并段的“内存工作区”越大，初始归并段越长

![外部排序10](https://wmicheng.top/images/note/img_Search_Sort/外部排序10.png)

## 败者树

> #### 问题引入（多路平衡带来的问题）

![败者树1](https://wmicheng.top/images/note/img_Search_Sort/败者树1.png)

> #### 定义

![败者树2](https://wmicheng.top/images/note/img_Search_Sort/败者树2.png)

> #### 败者树在多路平衡归并中的应用

> #### 败者树的存储结构

![败者树5](https://wmicheng.top/images/note/img_Search_Sort/败者树5.png)

**对于k路归并，第一次构造败者树需要对比关键字$k-1$次**

有了败者树，选出最小元素，只需对比关键字$[log_2k]$次

## 置换-选择排序

![败者树6](https://wmicheng.top/images/note/img_Search_Sort/败者树6.png)

使用置换-选择排序，可以让每个初始归并段的长度超过内存工作区大小的限制

![置换选择排序](https://wmicheng.top/images/note/img_Search_Sort/置换选择排序.png)

![置换选择排序1](https://wmicheng.top/images/note/img_Search_Sort/置换选择排序1.png)

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。

> #### 置换-选择算法的步骤如下

## 最佳归并树

- 归并过程中`磁盘I/O次数=归并树的WPL*2`（`重要结论`）
- **因此要让磁盘I/O次数最小，就要使归并树的WPL最小即构建一个`哈夫曼树`

> #### m叉最佳归并树的构造

![最佳归并树5](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树5.png)

- 注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树
- 则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造

![最佳归并树4](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树4.png)

> 增加虚段的数量

![最佳归并树6](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树6.png)

![最佳归并树7](https://wmicheng.top/images/note/img_Search_Sort/最佳归并树7.png)

## 总结

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

常见排序算法分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款