排序算法 小结

搜索算法的比较：

1. 稳定性

插入排序、冒泡排序、二叉树排序、归并排序及其他线性时间排序是稳定的；

选择排序、希尔排序（《资料》里没有总结）、快速排序、堆排序是不稳定的。

2. 时间复杂度

插入排序、冒泡排序、选择排序的时间复杂度为O(n2)；其它非线性时间排序的时间复杂度为O(nlogn)；

线性时间排序的时间复杂度为O(n)。

3. 辅助空间

线性时间排序、归并排序的辅助空间为O(n)，其它排序的辅助空间为O(1)。

4. 其它方面

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。在这种情况下，快速排序反而慢了。

当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序。

当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。

当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。