排序

published: 11/5/2018

Programming Data Structure

数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）

排序 (sorting) 的定义#

排序: 将一个数据元素（或记录）的任意序列重新排列成一个按关键字 有序 的序列。

• 升序：关键字从小到大
• 降序：关键字从大到小

排序的稳定性#

若序列中关键字值相等的节点经过某种排列方法进行排序之后，仍能保持它们在排序前的相对顺序，则称这种排序方法是 稳定 的；否则，称这种排序方法是 不稳定 的。

用符号表达： 在序列 $a_0$, $a_1$, $a_2$, … , $a_{n-1}$ 排序前 ( $a_i$ 对应关键字为 $k_i$) ，若 i < j ^ $k_i$ = $k_j$，且排序后，$a_i$ 一定仍在 $a_j$ 之前，则称这种排序方法是稳定的，否则这种排序方法是不稳定的。

排序的分类#

内存使用#

• 内部排序 排序期间全部节点都存储于内存，并在内存中调整等待排序节点的存放位置。

• 外部排序 排序期间大部分节点存储于外存中，排序过程中借助内存，调整那些存放在外存，等待排序的节点的存放值。

排序实现手段#

• 基于“比较-交换”的排序 如 插入排序、冒泡排序、快速排序、希尔排序、堆排序等。

• 基于“分配”的排序 如 基数排序、桶排序等。

实现难易#

• 基本排序方法 通常认为包括插入排序、冒泡排序、选择排序。

• 高级排序方法 如 快速排序、归并排序、堆排序等。

排序方法介绍#

基本排序方法#

冒泡排序#

插入排序#

高级排序#

快速排序#

归并排序#

性质#

• 稳定性

内容#

归并排序可分为 自下而上 和 自上而下 两种方式（本质相同） 先将数组拆分成许多很小的数组分别进行排序，然后小数组两两合并成较大的有序数组，较大的有序数组继续两两合并，重复该过程直至完全合并。

堆排序#

1. 构造出 堆 这种数据结构（可以用数组存储）
2. 得到所有数据中的最大/小值（位于堆的根节点上）
3. 将其与堆中末尾元素互换，堆元素数目减一
4. 调整堆，得到剩下的最值，重复操作

计数排序#

性质#

• 稳定性

内容#

创建一个和数据范围一样大的数组来存储每个数据出现次数

桶排序#

通过将所有数据根据大小均匀分配在 n 个桶中，然后对桶内的元素排序

1. 找出数组最值，确定桶的数目
2. 计算桶的大小，由此可得到每个桶存储数据的范围
3. 将待排序数据放入对应桶中
4. 在桶内部进行排序，并将所有桶合并以完成排序

基数排序#

基数排序分为 LSD(最低位优先法) 和 MSD(最高位优先法) 两种 中文

LSD#

1. 根据进制数 n 设置 n 元数组 count，count[i] 统计第 j 位数字为 i 的数的数目
2. 将 count 从前到后累加，即 count[i] = count[i] + count[i - 1](i 从 1 到 n - 1) ，得到 count[i] 即为 count[i] 所统计数字组在原数组中的结束位置
3. 根据 count 数组 从后向前 遍历原排序数组将每个数字放入数组中对应位置(第 j 位数字 i 对应的 count[i] - 1 即为对应位置)，同时更新 count 数组(count[i] 递减)
4. j 从最低位循环到最高位，即可完成排序

参考资料#

• 排序算法（三）：计数排序与桶排序 <- 这个靠谱
• 经典排序思想——桶排序
• 基数排序与计数排序
• 计数排序和基数排序和桶排序 <- 经典排序算法 - 计数排序Counting sort

推荐视频#

• 6 分钟演示 15 种排序算法 - Bilibili