排序
2022-01-03 本文已影响0人
Jimmy_Nie
1. 基本概念
排序方式
- 内排序：整个排序过程中，待排序的所有数据都放置于内存中
- 外排序：整个排序过程中，待排序的所有数据太多，不止放置于内存中，还需要部分放置于外存
2. 排序方式
算法稳定性：
定义：
- 假定在待排序的记录序列中，存在多个具有相同的关键字的记录；
- 若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，
- 而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的
应用：
如，一个商品之前按照价格高低排序了，此时需要按照销量排序，采用稳定算法，可以保证销量排序的前提下，保持价格的有序性
| 排序 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 逻辑思路 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(N2) | O(N) | O(N2) | O(1) | 稳定 | 与相邻元素两两比较 |
| 快速排序 | O(nlogn) | O(nlogn) | O(N2) | O(nlogn) ~ O(N) | 不稳定 |
冒泡排序升级版 1. 选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小 2. 再按此方法对这两部分数据分别进行快速排序 3. 整个排序过程可以递归进行，以此达到整个数据变成有序序列 |
| 简单选择排序 | O(N2) | O(N2) | O(N2) | O(1) | 稳定 | 选择集合中最小/大的元素放到最左边，然后是次小/大值，以此类推 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
简单选择排序的升级版 1.将待排序序列构造成一个大顶堆（根节点的值大于左右子节点），此时，整个序列的最大值就是堆顶的根节点 2. 将根节点与末尾元素进行交换，此时末尾就为最大值 3. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值 4. 如此反复执行，便能得到一个有序序列 |
| 直接插入排序 | O(N2) | O(N) | O(N2) | O(1) | 稳定 | 选择一个中间值，所有数字与该值比较； 根据比较结果，将其放置到中间值左边/右边 |
| 希尔排序 | O(nlogn) ~ O(N2) | O(N1/3) | O(N2) | O(1) | 不稳定 |
插入排序的升级版 1. 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序 2. 随着增量逐渐减少，每组包含的关键词越来越多 3. 当增量减至1时，整个文件恰被分成一组，算法便终止 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 采用经典的分治（divide-and-conquer）策略 1. 将问题分(divide)成一些小的问题然后递归求解 2. 治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之** |
2.1 简单排序
2.1.1 冒泡排序
2.1.2 选择排序
2.1.3 插入排序
2.2 希尔排序
2.3 堆排序
2.4 归并排序
2.5 快速排序
感觉如下这篇博客写的不错：
