Table of Content
数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）
排序 (sorting) 的定义
排序: 将一个数据元素（或记录）的任意序列重新排列成一个按关键字 有序 的序列。
- 升序：关键字从小到大
- 降序：关键字从大到小
排序的稳定性
若序列中关键字值相等的节点经过某种排列方法进行排序之后，仍能保持它们在排序前的相对顺序，则称这种排序方法是 稳定 的；否则，称这种排序方法是 不稳定 的。
用符号表达： 在序列 \(a_0\), \(a_1\), \(a_2\), ... , \(a_{n-1}\) 排序前 ( \(a_i\) 对应关键字为 \(k_i\)) ，若 i < j ^ \(k_i\) = \(k_j\)，且排序后，\(a_i\) 一定仍在 \(a_j\) 之前，则称这种排序方法是稳定的，否则这种排序方法是不稳定的。
排序的分类
内存使用
内部排序 排序期间全部节点都存储于内存，并在内存中调整等待排序节点的存放位置。
外部排序 排序期间大部分节点存储于外存中，排序过程中借助内存，调整那些存放在外存，等待排序的节点的存放值。
排序实现手段
基于“比较-交换”的排序 如 插入排序、冒泡排序、快速排序、希尔排序、堆排序等。
基于“分配”的排序 如 基数排序、桶排序等。
实现难易
基本排序方法 通常认为包括插入排序、冒泡排序、选择排序。
高级排序方法 如 快速排序、归并排序、堆排序等。
排序方法介绍
基本排序方法
冒泡排序
插入排序
高级排序
快速排序
归并排序
性质
- 稳定性
内容
归并排序可分为 自下而上 和 自上而下 两种方式（本质相同） 先将数组拆分成许多很小的数组分别进行排序，然后小数组两两合并成较大的有序数组，较大的有序数组继续两两合并，重复该过程直至完全合并。
堆排序
- 构造出
堆这种数据结构（可以用数组存储） - 得到所有数据中的最大/小值（位于堆的根节点上）
- 将其与堆中末尾元素互换，堆元素数目减一
- 调整堆，得到剩下的最值，重复操作
计数排序
性质
- 稳定性
内容
创建一个和数据范围一样大的数组来存储每个数据出现次数
桶排序
通过将所有数据根据大小均匀分配在 n 个桶中，然后对桶内的元素排序
- 找出数组最值，确定桶的数目
- 计算桶的大小，由此可得到每个桶存储数据的范围
- 将待排序数据放入对应桶中
- 在桶内部进行排序，并将所有桶合并以完成排序
基数排序
基数排序分为 LSD(最低位优先法) 和 MSD(最高位优先法) 两种 中文 ##### LSD
- 根据进制数 n 设置 n 元数组 count，count[i] 统计第 j 位数字为 i 的数的数目
- 将 count 从前到后累加，即
count[i] = count[i] + count[i - 1](i 从 1 到 n - 1) ，得到 count[i] 即为 count[i] 所统计数字组在原数组中的结束位置 - 根据 count 数组 从后向前 遍历原排序数组将每个数字放入数组中对应位置(第 j 位数字 i 对应的 count[i] - 1 即为对应位置)，同时更新 count 数组(count[i] 递减)
- j 从最低位循环到最高位，即可完成排序