排序——排序算法总结

稳定性比较：

• 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线性排序是稳定的。
• 选择排序、希尔排序、快速排序、堆排序是不稳定的，即有跨度的交换都会导致不稳定。

时间复杂度比较：‘

• $O(^2)$：插入排序、冒泡排序、选择排序

• $O(n \log n)$：快速排序、堆排序、归并排序

• $O(n)$：桶排序

从最好情况考虑，插入排序和冒泡排序时间复杂度最好，为$O(n)$，其他算法最好情况和平均情况相同。从最坏情况考虑，快速排序的时间复杂度是$O(n^2)$，插入排序和冒泡排序虽然和平均情况相同，但是系数增加一倍；对选择排序、堆排序和归并排序影响不大。

桶排序、归档排序的辅助空间为$O(n)$，快速排序的辅助空间为$O(\log n)$，最坏情况为$O(n)$，其他为$O(1)$。