博客

根据排序过程中借助的主要操作，将7种内排序算法按照下图所示进行分类。

将7种算法的各种指标进行对比，如下表所示。

从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简单算法。

从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果待排序列总是基本有序，反而不应该考虑四种复杂的改进算法。

从最快情况看，堆排序与归并排序又强过快速排序以及其他简单排序。

从空间复杂度来说，如果执行算法的软件所处的环境非常在乎内存使用量的多少时，应该选择堆排序。

从稳定性来看，归并排序是个好算法。

从待排序记录的个数上来说，待排序的个数n越小，采用简单排序算法更合适。反之，n越大，采用改进算法越合适。

总之，综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同场合也应该考虑使用不同的算法。