1 排序的基本概念
假设含有 n 个记录的序列为{r1,r2,…,rn} ，其相应的关键字分别为{k1,k2,…,kn} ，需确定 1,2,…,n 的一种排列 p1,p2,…,pn，使其相应的关键字满足 kpl<=kp2<=…<=kpn (非递减或非递增) 关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,…,rpn}，这样的操作就称为排序 。
2 排序的稳定性
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若相对次序发生变化，则称这种排序方法是不稳定的。
3 排序的分类
- 内排序：在排序整个过程中，待排序的所有记录全部被放置在内存中。
- 插入排序
- 直接插入排序
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 直接选择排序
- 堆排序
- 归并排序
- 分配排序
- 计数排序
- 桶排序
- 基数排序
- 插入排序
- 外排序：由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。
- 合并排序法
- 直接合并排序法
4 各种内部排序算法的比较
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 直接选择排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n2) | O(n1/3) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)~O(n) | 不稳定 |
- 简单算法：冒泡、简单选择、直接插入。
- 改进算法：希尔、堆、归并、快速。
从平均情况来看，显然最后 3 种改进算法要胜过希尔排序，并远远胜过前 3 种简单算法。
从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑 4 种复杂的改进算法。
从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。