0. 总览
10大排序算法
- 以上表格是基于 数组 进行排序的一般性结论
- 稳定性：如果相等的2个元素，在排序前后的 相对位置保持不变，此为 稳定的排序算法
- In-Place：原地算法，不依赖额外的资源 或者 依赖少数的额外资源，仅依靠输出 来 覆盖输入
- 冒泡、选择、插入、归并、快速、希尔、堆排序，属于 比较排序（Comparision Sorting）
1. 冒泡排序（Bubble Sort）
冒泡排序
(1) 执行流程
从头开始比较每一对 相邻元素，如果第1个比第2个 大，就交换它们的位置
执行完一轮后，最末尾的那个元素就是最大的元素忽略①中曾经找到的最大元素，重复执行步骤①，直到全部元素有序
(2) 优化方案
- 如果序列已经 完全有序，可提前终止冒泡排序
- 如果序列尾部已经 局部有序，可记录最后1次交换的位置，减少比较次数
(3) 复杂度分析
- 最好时间复杂度：
- 最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
2. 选择排序（Selection Sort）
选择排序
(1) 执行流程
从序列中找出 最大的那个元素，与 最末尾的元素 交换位置
执行完一轮后，最末尾的那个元素就是最大的元素忽略①中曾经找到的最大元素，重复执行步骤①，直到全部元素有序
(2) 优化方案
- 使用 堆 来选择最大值
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 不稳定排序
3. 堆排序（Heap Sort）
堆排序
(1) 执行流程
对序列进行原地建堆（heapify）
重复执行以下操作，直到堆的元素数量为1
① 交换堆顶元素 与 为尾元素
② 堆的元素数量减1
③ 对0位置进行1次 siftDown操作
(2) 优化方案
- 堆排序 可以认为是对 选择排序 的一种优化
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 不稳定排序
4. 插入排序（Insertion Sort）
插入排序
(1) 执行流程
在执行过程中，插入排序会将序列分为2部分
头部是已经排好序的，尾部是待排序的从头开始扫描每一个元素
每当扫描到一个元素，就将它插入到头部合适的位置，使头部数据依然保持有序
(2) 优化方案
- 方案一：将【交换】转为【挪动】
① 先将待插入的元素备份
② 头部有序数据中 比 待插入元素大的，都朝尾部方向挪动1个位置
③ 将待插入元素 放到最终的合适位置 - 方案二：二分搜索
① 假设在 [begin, end) 范围内搜索某个元素v， mid = (begin + end) / 2
② 如果 v < m，去 [begin, mid) 范围内二分搜索
③ 如果 v > m，去 [mid + 1, end) 范围内二分搜索
④ 如果 v = m，直接返回 mid
(3) 复杂度分析
- 最好时间复杂度：
- 最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
5. 归并排序（Merge Sort）
归并排序
(1) 执行流程
不断地将当前序列 平均分割成 2个子序列 - divide分割操作
直到不能再分割（序列中只剩1个元素）不断地将2个子序列 合并成 一个有序序列 - merge归并操作
直到最终只剩下1个有序序列
(2) 优化方案
- 无
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
6. 快速排序（Quick Sort）
快速排序
(1) 执行流程
从序列中选择一个轴点元素（pivot）
假设每次选择 0位置的元素 为轴点元素利用 pivot 将序列分割成 2个子序列
将小于 pivot 的元素放在 pivot前面(左侧)
将大于 pivot 的元素放在 pivot后面(右侧)
将等于 pivot 的元素放在 pivot任意一侧对 子序列进行 ① ② 操作
直到不能再分割（子序列中只剩下1个元素）
- 快速排序的本质：逐渐将每一个元素都转换成 轴点元素
(2) 优化方案
- 随机选择轴点元素 - 降低最坏情况的出现概率
(3) 复杂度分析
- 最好、平均时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：
- 不稳定排序
7. 希尔排序（Shell Sort）
希尔排序
希尔排序图解
(1) 执行流程
把序列看作是一个 矩阵，分成m列，逐列进行排序
m 从某个整数逐渐减为1
当m为1时，整个序列完全有序
(2) 优化方案
- 矩阵的列数取决于 步长序列，选择最好的步长序列
- 其最坏时间复杂度是
(3) 复杂度分析
- 最好、平均时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：
- 不稳定排序
- 冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于 比较的排序
- 平均时间复杂度最低是
- 计数排序、桶排序、基数排序，都不是基于 比较的排序
- 典型的 用空间换时间，在某些时候，平均时间复杂度可以比
更低
8. 计数排序（Counting Sort）
计数排序
(1) 执行流程
核心思想：统计每个整数 在序列中出现的 次数，进而推导出每个整数 在有序序列中的索引。
(2) 优化方案
- 计数数组 区间为 [min, max]
- 每个元素累加上 其前面的所有元素，得到元素在有序序列中的位置信息
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
*（k是整数的取值范围）
9. 基数排序（Radix Sort）
基数排序
(1) 执行流程
依次对 个位数、百位数、千位数、万位数... 进行排序（从低位到高位）
(2) 优化方案
- 无
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
- （d是最大值得位数，k是进制）
9. 桶排序（Bucket Sort）
桶排序
(1) 执行流程
- 创建一定数量的桶
- 按照一定的规则，将序列中的元素 均匀分配到对应的桶
- 分别对每个桶进行 单独排序
- 将所有非空桶的元素 合并成有序序列
(2) 优化方案
- 无
(3) 复杂度分析
- 最好、最坏、平均时间复杂度：
- 空间复杂度：
- 稳定排序
- （m 是桶的数量，k 为
）
