排序算法

一、排序的第一性原理

1. 排序的本质

排序 = 将一个无序集合，转换为满足某种全序关系的序列。

从信息视角看，排序解决的是：

• 元素之间相对顺序不确定的问题
• 系统如何通过操作逐步消除不确定性

2. 有序度与逆序度模型

$$ \text{有序度} = \sum_{i<j}\delta(Ai < Aj) $$

• 满有序度：完全有序时的有序度
• 逆序度 = 满有序度 − 当前有序度

排序过程的本质：不断减少逆序对的过程。

不同排序算法的区别，不在于“是否排序”，而在于：

• 如何发现逆序
• 如何消除逆序
• 一次消除多少逆序

3. 排序算法的两种信息来源

二、排序算法的认知结构树

排序算法
├── 比较排序
│   ├── 插入型（插入、希尔）
│   ├── 交换型（冒泡、快速）
│   ├── 选择型（选择、堆）
│   └── 分治型（归并、快速）
└── 非比较排序
    ├── 计数（计数排序）
    ├── 映射（桶排序）
    └── 位分解（基数排序）

分类的目的不是记忆，而是理解算法之间的血缘关系。

三、排序算法的评价维度（设计代价）

稳定性本质：

稳定排序 = 不跨越相等元素

四、基础比较排序（O(n²) 的意义）

O(n²) 排序不是“低级算法”，而是：

• 小规模最优解
• 复杂排序的子过程
• 有序度敏感算法

1. 选择排序（选择型）

核心思想：

• 每一轮选择“当前最小值”
• 直接放入最终位置

哲学代价：

• 交换次数少
• 不关心已有顺序 → 不稳定

2. 插入排序（插入型）

核心思想：

• 假设前缀有序
• 将新元素插入正确位置

本质优势：

• 对逆序度敏感
• 近乎有序时接近 O(n)

3. 冒泡排序（交换型）

核心思想：

• 相邻比较
• 将最大（最小）值逐步“冒”到边界

本质问题：

• 只能消除局部逆序
• 信息利用率低

五、插入思想的跃迁：希尔排序

本质创新：

用“间隔插入”提前消除远距离逆序。

• 插入排序的加速版
• 通过增量序列逐步逼近完全有序

代价：

• 理论复杂度难以精确分析
• 不稳定

六、分治范式的两种极端

1. 归并排序（稳定 + 空间换时间）

本质模型：

• 分解问题规模
• 合并局部有序结构

哲学取舍：

• 用 O(n) 空间换取稳定的 O(nlogn)

外部归并排序

面向磁盘与 IO 的排序范式。

2. 快速排序（局部性最优解）

本质模型：

• 通过 partition 建立局部有序
• 递归放大局部优势

风险：

• 极端情况下退化为 O(n²)

双路 / 三路快排

本质是：控制等值元素导致的结构退化。

七、突破比较下界：线性排序

1. 桶排序（分布假设）

stateDiagram-v2
1 2 3 4 5 6 7 8 9
1 --> [1,3]
2 --> [1,3]
3 --> [1,3]
4 --> [4,6]
5 --> [4,6]
6 --> [4,6]
7 --> [7,9]
8 --> [7,9]
9 --> [7,9]

本质前提：

• 数据分布近似均匀

2. 计数排序（值到位置的映射）

核心思想：

• 用下标直接表示“位置”
• 完全消除比较

约束：

• 非负整数
• 范围有限

3. 基数排序（位分解）

hke          iba        hac         hac
iba          hac        iba         hke
hzg  ->      hke  ->    hke    ->   hzg
ikf          ikf        ikf         iba
hac          hzg        hzg         ikf

本质模型：

将复杂比较，分解为多轮稳定的简单排序。

八、特殊排序的认知定位

猴子排序 / 睡眠排序

不是工程算法，而是：

• 概率
• 并发
• 随机性思想的极端展示

九、洗牌算法（排序的对偶问题）

Fisher-Yates / Knuth-Durstenfeld

排序：消除不确定性 洗牌：制造不确定性

二者在概率模型上是对偶问题。

十、工程选型决策模型

结语

排序算法不是技巧集合，而是工程世界中"秩序建立"的思想样本。

理解排序，本质是在理解：

• 信息如何被逐步确认
• 系统如何在约束下达成有序
• 工程设计中的权衡哲学