前言
算法对比：
时空复杂度、算法的稳定性、算法的过程特征
时间复杂度
简单选择排序、直接插入排序和冒泡排序平均情况是 O(n^2^)
直接插入排序和冒泡排序最好情况是 O(n)
简单选择排序与初始状态无关（需要遍历求出最小或者最大的数字）
希尔排序对大规模的的排序可以达到很高的效率
堆排序可以在线性时间内完成建堆
快速排序基于分治思想，平均性能可以达到 O(nlog2n),在实际应用中常常由于其他算法
归并排序也基于分治思想，最好最坏平均时间复杂度都是O(nlog2n)
空间复杂度
简单选择排序、插入排序、冒泡排序、希尔排序和堆排序仅需要常数个辅助空间
快速排序需要使用一个小的辅助栈完成递规，平均大小 O(log2n)，最坏情况是 O(n)
2路归并排序在合并操作中需要借助较多的辅助空间完成复制，大小 O(n)
稳定性
插入排序、冒泡排序、归并排序、基数排序是稳定的排序方法
简单选择排序、快速排序、希尔排序、堆排序是不稳定的
过程特征
快速排序在一趟处理后就能确定一个元素的最终位置
冒泡和堆排序每趟处理都能产生当前的最大值或最小值
总结
算法|时间最好|时间平均|时间最坏|空间|稳定|
-|-|-|-|-|-|-|-
直接插入排序|O(n)|O(n2)|O(n2)|O(1)|是
冒泡排序|O(n)|O(n2)|O(n2)|O(1)|是
简单选择排序|O(n2)|O(n2)|O(n2)|O(1)|否
希尔排序|-|-|-|O(1)|否
快速排序|O(nlog2n)|O(nlog2n)|O(n2)|O(log2n)|否
堆排序|O(nlog2n)|O(nlog2n)|O(nlog2n)|O(1)|否
2路归并排序|O(nlog2n)|O(nlog2n)|O(nlog2n)|O(n)|是
基数排序|O(d(n + r))|O(d(n + r))|O(d(n + r))|O(r)|是
