种类	时间复杂度	是否基于比较
比较,冒泡,选择	\(n^2\)	是
快排,归并	\(nlogn\)	是
桶排序,基数排序	\(n\)	否

评价排序算法的几个角度

1. 执行效率
   • 比较交换的次数
   • 时间复杂度的系数,常数,低阶,因为实际开发中数据规模小,这些系数等影响算法性能
   • 最好,最坏,平均时间复杂度
2. 内存消耗,即空间复杂度

   原地排序,空间复杂度是O(1)的算法

3. 稳定性
   在待排序的序列中存在等值元素,排序后等值元素顺序不变.
   应用:实际开发中,对一组对象按照某个key排序,eg:对订单排序,其中有下单时间和订单金额.

冒泡

1. 原地排序
2. 稳定,换对于相等元素,不交
3. 最好时间复杂度O(1),最坏O(//(n^2//),平均O(n\(n^2\)),最好情况,冒泡一次结束

插入

1. 原地
2. 稳定,相等元素,后出现的插在先出现的后面
   3. 最好时间复杂度O(1),最坏O(//(n^2//),平均O(n\(n^2\))不理解

冒泡,插入,选择

1. 原地排序

2. 最好时间复杂度O(1),最坏O(//(n^2//),平均O(n\(n^2\)),最好情况,冒泡一次结束

选择的最好最坏平均都是(//(n^2//)

3. 冒泡和插入 稳定排序
   选择 不稳定排序

   冒泡:对于相等元素,不交换
   插入:相等元素,后出现的插在先出现的后面
   选择:例如5,8,5,2,9 第一次交换第一个5就被交换到后面了

插入好于冒泡的原因

冒泡的交换次数和插入的移动次数都等于原始数据的逆序度,无法优化.

但是,冒泡需要三个赋值操作,插入需要一个赋值操作

插入排序的优化,希尔排序

---

课后习题: 基于链表实现的排序

三者,比较次数一致,冒泡和选择,交换操作复杂,插入交换操作简单,直接插入不需要移动数组

---

归并的性能分析

1. 稳定性
2. 时间复杂度
3. 空间复杂度

归并和快排的差异

归并是由下到上,先处理子问题,再合并
快排是由上到下,先分区再处理子问题

快排的性能分析

1. 稳定性 不稳定
2. 时间复杂度
3. 空间复杂度 原地

归并的重点: 是递推公式和merge()合并函数
快排的重点: 是递推公式和partition()分区函数

---

线性排序
时间复杂度是线性

桶排序,计数排序,基数排序

桶排序对数据要求:

1. 能很容易分成m个桶
2. 桶与桶之间有天然大小顺序
3. 数据再每个桶之间的分布是均匀的

适用于外部排序:数据储存在磁盘中,数据量大,内存有限

基数排序对数据的要求:

1. 可以分割出独立的位
2. 位之间有递进关系
3. 每一位的数据范围不能太大,可以用线性算法排序,否则时间复杂度无法是O(n)