一、分类
常用的排序有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序等。
前三个理解起来相对简单，分类为简单排序。基于元素比较进行，时间复杂度都为O(n²)。
中间两个，归并 & 快排，复杂一些，但思路比较统一。基于元素比较进行，时间复杂度都为O(n log n)。
后面三个解决问题的思路特殊，并非基于比较进行，对数据有一定要求，但时间复杂度可以做到O(n)。
二、如何考量一个排序算法的好坏
2.1 时间复杂度
时间复杂度也要区分最好情况、最坏情况、平均情况的时复杂度。
2.2 空间复杂度（内存消耗）
如果无需额外空间，及空间复杂度为O(1)，也称为原地排序。
2.3 稳定性
即值相同的元素在排序前后的顺序性是否保持一致的描述，如果保持一致，则称为稳定排序，反之为非稳定排序。
三、简单排序
3.1 冒泡排序
每进行一轮冒泡，保证将最大的元素冒到未排序序列的最后面。即第n轮冒泡后，序列的后n个值的序列变为有序。
3.2 插入排序
序列分为有序部分和无序部分，每次选择无序序列的第一个与依次与有序序列的值进行比较，插入到正确的位置。
3.3 选择排序
序列分为有序部分和无序部分，每次找到无需序列中的最小值，放到有序序列的末尾加入有序序列。
四、简单排序的对比
| 排序算法 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 是 |
| 插入排序 | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(1) | 否 |
可以看到三种排序的平均时间复杂度都是O(n²)，空间复杂度都是O(1)，即都是原地排序。
但冒泡和插入都是稳定的，选择排序是非稳定的。这点可以从它们的实现策略上分析出来，冒泡和插入都是数据依次对比，我们可以决定相等时的策略（交换or不交换、插入在前or插入在后）。而选择排序的跨位置交换，可能造成原序列中相等元素的相对位置改变。