===============
== 大程熙 ==
===============
一个小学生

算法之各类排序算法总结比较

各类排序算法总结和比较。

汇总

算法分类 排序算法 时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 备注
插入排序 直接插入排序 $O(n^2)$ O(n) $O(n^2)$ O(1) 稳定
插入排序 二分插入排序 $O(n^2)$ $O(nlog_{2}n)$ $O(n^2)$ O(1) 稳定 是对直接插入排序的优化,查找过程改为二分查找
插入排序 希尔排序 依赖于增量序列 不稳定
插入排序 成对插入排序 是对直接插入排序的优化,一次进行两个元素的直接插入比较
交换排序 冒泡排序 $O(n^2)$ O(n) $O(n^2)$ O(1) 稳定
交换排序 快速排序 $O(n \times log_{2}n)$ $O(n^2)$ $O(n \times log_{2}n)$ 介于$O(log_{2}n)$和$O(n)$ 不稳定 赋值填充方式、两端扫描交换方式、单向扫描划分、三分单向扫描、三分双向扫描
交换排序 双轴快排 是对快排的优化,使用两个基准点
选择排序 直接选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ O(1) 不稳定
选择排序 堆排序 $O(n \times log_{2}n)$ $O(n \times log_{2}n)$ $O(n \times log_{2}n)$ O(1) 不稳定
归并排序 归并排序 $O(n \times log_{2}n)$ $O(n \times log_{2}n)$ $O(n \times log_{2}n)$ O(n) 稳定

应用场景

排序算法中用到的操作有:比较、移动、交换。这些操作的次数多少直接影响到排序算法的效率。需要在不同的场景中选择不同的排序算法,像直接插入排序、冒泡排序、直接选择排序,数据的比较和移动都在相邻的两个元素之间进行,存在较多的重复比较、移动和交换,效率比较低。而对于希尔排序、快速排序、堆排序、归并排序,这些排序算法尽可能少的比较和移动数据,从而提升效率。

  • 数据较少的情况下,比如几十个数据进行比较,可以使用直接插入排序或者是直接选择排序。
  • 如果数据较多,可以使用快速排序、堆排序、归并排序,现在可以使用更好地双轴快排。
  • 如果数据基本有序,可以使用直接插入排序、快排、冒泡排序。

参考内容

  • 《数据结构(Java版)》