Intro
定义
所谓排序就是将一个序列的元素，按照某种偏序关系，递增或递减的排列起来。
排序算法的分类
按排序方式
本章会将上述排序算法进行一一的介绍。
按数据存放位置
- 内排序：数据元素放在内存中的排序。
- 外排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能再内外存之间移动数据的排序。
排序性能
比较排序
| 时间复杂度 | 空间复杂度 | 稳定性 | |
|---|---|---|---|
| 插入排序 | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 希尔排序 | \(O(n\log^2{n})\) | \(O(1)\) | 不稳定 |
| 选择排序 | \(O(n^2)\) | \(O(1)\) | 不稳定 |
| 堆排序 | \(O(n\log{n})\) | \(O(1)\) | 不稳定 |
| 冒泡排序 | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 快速排序 | \(O(n\log{n})\) | \(O(n\log{n})\) | 不稳定 |
| 归并排序 | \(O(n\log{n})\) | \(O(n)\) | 稳定 |
非比较排序
| 时间复杂度 | 空间复杂度 | 稳定性 | |
|---|---|---|---|
| 计数排序 | \(O(n)\) | \(O(n)\) | 稳定 |
| 桶排序 | \(O(n)\sim O(n^2)\) | \(o(n)\) | 稳定 |
| 基数排序 | \(O(n\log{n})\) | \(O(n)\) | 稳定 |