排序算法_十大排序算法总结

  排序算法可以分为内部排序和外部排序&＃xff0c;内部排序是数据记录在内存中进行排序&＃xff0c;而外部排序是因排序的数据很大&＃xff0c;一次不能容纳全部的排序记录&＃xff0c;在排序过程中需要访问外存。

  十种常见排序算法可以分为两大类&＃xff0c;如下图所示。

1. 比较类排序&＃xff1a; 通过比较来决定元素间的相对次序&＃xff0c;由于其时间复杂度不能突破$O(nlogn)$&＃xff0c;因此也称为非线性时间比较类排序。
2. 非比较类排序&＃xff1a; 不通过比较来决定元素间的相对次序&＃xff0c;它可以突破基于比较排序的时间下界&＃xff0c;以线性时间运行&＃xff0c;因此也称为线性时间非比较类排序。

  常见排序算法简介如下表所示。

  结论&＃xff1a; 1. 当初始序列基本有序时&＃xff0c;直接插入排序最快&＃xff0c;快速排序慢&＃xff08;在初始序列较为混乱时快&＃xff09;&＃xff1b;
      2. 归并排序对初始序列排序不敏感&＃xff0c;速度稳定&＃xff1b;
      3. 记录个数较少&＃xff0c;采用插入排序或选择排序&＃xff0c;记录本身信息量大&＃xff0c;采用简单选择排序&＃xff1b;
      4. 记录较大&＃xff0c;采用快速排序、堆排序、归并排序。