概念

约 285 字小于 1 分钟

概念

排序open in new window是重新排列一系列对象以使它们按某种逻辑顺序排列的过程。

验证

验证
- 对数器，保证算法正确性
- 运行时间，算法的稳定性
- 空间复杂度
  - 函数调用栈，递归
  - 固定数量变量
  - 额外数组
- Benchmark 时间复杂度相同，仅仅因为指令集不同
比较器 Comparable，根据语言非必选
稳定性假设 $K_i$ $K_{i}$ = $K_j$ $K_{j}$ （1 ≤ i ≤ n，1 ≤ j ≤ n，i ≠ j），且在排序前的序列中 $K_i$ $K_{i}$ 领先于 $K_j$ $K_{j}$ （即 i < j）。
- 若在排序后的序列中 $K_i$ 仍领先于 $K_j$ ，则称所用的排序方法是稳定的；
- 反之，若可能使排序后的序列中 $K_j$ 领先于 $K_i$ ，则称所用的排序方法是不稳定的。

常见排序

插入类
- 插入排序
- 折半插入排序
- 希尔排序
交换类
- 冒泡排序
- 快速排序
选择类
- 选择排序
- 树形选择排序
- 堆排序
归并类
- 归并排序
分配类
- 计数排序
- 桶排序
- 基数排序