排序算法简介
排序
- 排序成有序的顺序表则可以采用查找效率较高的二分法(折半查找法)，而无序只能进行顺序查找
- 排序两大类：
- 内部排序：待排序内容不大可以存放再计算机内存中进行排序
- 外部排序：带排序内容很大，需要借助外存进行排序，一般会用归并排序，因为归并不需要一次性把所有数据都存入内存
- 内部排序：
- 根据不同原则进行分类：(1)插入排序，(2)交换排序，(3)选择排序，(4)归并排序，(5)基数排序
- 根据所需工作量区分：(1)简单的排序：时间复杂度 O(n^2)，(2)先进的排序：时间复杂度 O(n logn) <--log 是以 2 为底，(3)基数的排序：时间复杂度 O(d n)
- 时间复杂度的 n 表示 数据增大 n 倍，假设 O(log256) 则表示数据增大 256 倍，其时间复杂度仅仅增大 8 倍
内部排序时间空间复杂度
| 算法名 | 最优 Time | 平均 Time | 最差 Time | Space |
|---|---|---|---|---|
| Radix Sort(基数) | O(n+m) | O(k (n+m)) | O(k (n+m)) | O(m) |
| Quick Sort(快排) | O(n logn) | O(n logn) | O(n ^2) | O(logn) |
| Merge Sort(归并) | O(n logn) | O(n logn) | O(n logn) | O(n) |
| Heap Sort(堆排) | O(n logn) | O(n logn) | O(n logn) | O(1) |
| Shell Sort(希尔) | O(n^(1.3)) | 与增量取值有关 | O(n^(2)) | O(1) |
| Binary Sort(二分法) | O(n) | O(n^2) | O(n^2) | O(1) |
| Insert Sort(直接插入) | O(n) | O(n^2) | O(n^2) | O(1) |
| Select Sort(简单选择) | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Bubble Sort(冒泡) | O(n^2) | O(n^2) | O(n^2) | O(1) |
选择排序 和 交换排序：
选择法基本思路与交换法大致相似，不同点是交换法在一轮中要 "比较交换多次"，而选择法是一轮中比较多次，而"最多交换一次"