排序算法的比较

排序算法的比较

从时间复杂度上来看

简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为O（n^2），且实现过程也较为简单，但直接插入排序和冒泡排序最好情况下的时间复杂度的时间复杂度可以达到O(n)，而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆。且在O（nlog2n）内完成排序过程。快速排序基于分治的思想，虽然最坏情况下快速排序时间会达到O(n ^ 2),但快速排序平均性能可以达到O（nlog2n），在实际应用中常常优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排序无关，因此它的最好、最坏和平均时间复杂度均为O(nlog2n)。

从空间复杂度来看

简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间。快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小为O(log2n)，当然在最坏情况下可能会增长到O(n)。2路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为O(n)，虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

从稳定性看

插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。

其他特点

冒泡排序和堆排序在每趟处理后都能产生当前的最大值和最小值 快速排序一趟处理就能确定一个元素的最终位置