排序算法
简介
在计算机科学与数学中，排序算法（英语：Sorting algorithm）是一种能将数据依照特定顺序排列的算法。排序后的数据可存储在有序数组中。
常见的排序方式：
- 数值顺序
- 字典顺序
排序算法在搜索算法、合并算法、文字处理及输出格式化等领域都有重要应用。
排序算法的结果必须满足：
- 输出为递增（或递减）序列，依排序要求而定。
- 输出是输入的一种排列或重组。
虽然排序问题看似简单，但已有大量研究。例如，冒泡排序早在1956年就已提出。至今仍不断有新算法出现，如图书馆排序（2004年）。
分类标准
排序算法常按以下指标分类：
- 时间复杂度（最差、平均、最好性能）
- 常见复杂度：
- 好的：
O(n log n) - 坏的：
O(n²) - 理想：
O(n)（基于比较的排序通常至少为O(n log n)）
- 好的：
- 常见复杂度：
- 内存使用量（额外空间及系统资源消耗）
- 稳定性
稳定排序会保持相等键值记录的原有相对顺序。 - 排序方法
- 插入
- 交换
- 选择
- 合并
- 其他
稳定性说明
例子：按第一个数字排序的数对：
1 | (4,1) (3,1) (3,7) (5,6) |
- 稳定排序结果：
1 | (3,1) (3,7) (4,1) (5,6) |
- 不稳定排序结果：
1 | (3,7) (3,1) (4,1) (5,6) |
不稳定排序可能改变相等键值中记录的相对次序，稳定排序则不会。
排序算法列表
稳定排序
- 冒泡排序（Bubble sort）—
O(n²) - 插入排序（Insertion sort）—
O(n²) - 鸡尾酒排序（Cocktail sort）—
O(n²) - 桶排序（Bucket sort）—
O(n)；需O(k)空间 - 计数排序（Counting sort）—
O(n+k)；需额外O(n+k)空间 - 归并排序（Merge sort）—
O(n log n)；需O(n)空间 - 原地归并排序 —
O(n log² n)（最佳版本） - 二叉排序树排序（Binary tree sort）— 平均
O(n log n)，最坏O(n²)；需O(n)空间 - 鸽巢排序（Pigeonhole sort）—
O(n+k)；需O(k)空间 - 基数排序（Radix sort）—
O(nk)；需O(n)空间 - 侏儒排序（Gnome sort）—
O(n²) - 图书馆排序（Library sort）— 平均
O(n log n)，最坏O(n²) - 块排序（Block sort）—
O(n log n) - Tim排序（Timsort）— 平均/最坏
O(n log n)，最佳O(n)；需O(n)空间
不稳定排序
- 选择排序（Selection sort）—
O(n²) - 希尔排序（Shell sort）—
O(n log² n)（最佳版本） - 克洛弗排序（Clover sort）— 平均
O(n)，最坏O(n²) - 梳排序（Comb sort）—
O(n log n) - 堆排序（Heap sort）—
O(n log n) - 平滑排序（Smooth sort）—
O(n log n) - 快速排序（Quick sort）— 平均
O(n log n)，最坏O(n²) - 内省排序（Introsort）—
O(n log n) - 耐心排序（Patience sort）— 最坏
O(n log n + k)；需O(n+k)额外空间
非实用排序
- Bogo排序 —
O(n × n!)（期望时间可能无穷） - Stupid排序 —
O(n³)（递归版O(n²)） - 珠排序 —
O(n)或O(√n)（需特殊硬件） - 煎饼排序 —
O(n)（需特殊硬件） - 臭皮匠排序 —
O(n^{2.7})
部分排序算法比较表
| 排序算法 | 数据结构 | 稳定性 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 描述 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 数组 | 稳定 | O(n²) |
O(n²) |
O(1) |
每轮把最大元素交换到末尾 |
| 选择排序 | 数组 | 不稳定 | O(n²) |
O(n²) |
O(1) |
每轮选择最小元素放到前面 |
| 插入排序 | 数组/链表 | 稳定 | O(n²) |
O(n²) |
O(1) |
每次将未排序元素插入有序序列 |
| 堆排序 | 数组 | 不稳定 | O(n log n) |
O(n log n) |
O(1) |
用最大堆取出最大值 |
| 归并排序 | 数组 | 稳定 | O(n log n) |
O(n log n) |
O(n) |
分治法合并两有序段 |
| 快速排序 | 数组 | 不稳定 | O(n log n) |
O(n²) |
O(log n) |
选基准分区后递归排序 |
| 希尔排序 | 数组 | 不稳定 | O(n log² n) |
O(n²) |
O(1) |
按间隔分组执行插入排序 |
| 计数排序 | 数组 | 稳定 | O(n+m) |
O(n+m) |
O(n+m) |
计数映射元素位置 |
| 桶排序 | 数组/链表 | 稳定 | O(n) |
O(n²) |
O(m) |
使用桶分布数据 |
| 基数排序 | 数组/链表 | 稳定 | O(k × n) |
O(k × n) |
O(n+k) |
多关键字排序 |
参考链接
- 标题: 排序算法
- 作者: 星隐
- 创建于 : 2025-11-29 14:12:33
- 更新于 : 2026-01-19 01:58:27
- 链接: https://www.starin.top/post/67d6da0edb8b/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。