几种排序算法总结
排序的定义
对一序列对象根据某个关键字进行排序。
这里简单总结下各种排序的特点：
画个表
稳定性：若a=b，排序后相对位置不变即稳定，否则为不稳定
时间复杂度：一个算法执行所耗费的时间
空间复杂度：一个算法执行所耗费的内存
排序方式：内排序—在内存中完成排序，外排序—在硬盘中完成排序
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 | |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | In-place | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | In-place | 稳定 |
| 希尔排序 | O(n log n) | O(n log2n) | O(n log2n) | O(1) | In-place | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) | In-place | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n2) | O(n + k) | Out-place | 稳定 |
| 基数排序 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | Out-place | 稳定 |
冒泡排序
从最简单的冒泡排序开始总结，差不多是每个人接触的第一个排序算法。它重复地在排序的数列上跑，一次比较两个元素，如果顺序不对就把他们两个互相交换，每次从头开始，每次完成一个。
选择排序
每次选择序列中最小的第一个放到未排序序列的起始位置，这个元素就是已排好序列了，然后继续在未排序的序列中找最小值，放到已排序序列的末尾，以此类推。
插入排序
插入排序像玩扑克牌一样排序，对于一个未排序的序列，一个一个往前扫描，当它大于前面的数并且小于后面的数时，将这个数插入到这个位置，此时这一段数列就是排序后的序列了，再将未排序序列中的元素从后往前和排序完成的序列挨个比较，以此类推。
未完待续
