文章目录
  1. 1. 排序总结
    1. 1.1. 算法指标对比

排序总结

这几天一直在写排算法,这属于最基本的算法,以前只是知道,也没怎么用过,最近重新温故复习,总结一下。
其实排序分为内部排序和外部排序,区别在于是否将排序记录全部放置在内存中,外部排序主要用于大量数据的排序,如多路归并排序。最近几天写的都是内部排序。主要可以分为四类:

  1. 插入类排序:直接插入排序和希尔排序。
  2. 选择类排序:简单选择排序和堆排序。
  3. 交换排序类:冒泡排序和快速排序。
  4. 归并类排序:归并排序。

简单的算法:冒泡、简单选择、直接插入。
改进的算法:希尔、堆、归并、快速。

算法指标对比

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
直接插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^3/2) O(n^2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(1) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定

算法的选择则需要根据需要选择,比如追求稳定性来说归并排序是个好选择,但是会牺牲空间复杂度。 再比如数据量不大但是关键字信息量大(如数字很大),交换和移动次数多则会耗费和迪诺时间,此时应该选择移动次数较少的简单排序算法。

文章目录
  1. 1. 排序总结
    1. 1.1. 算法指标对比