7种排序总结

基本概念

排序稳定性: 假设k_i = k_j, 且排序在排序前的序列k_i领先于k_j. 如果排序后k_i仍领先于k_j, 则称所用的排序方法是稳定的; 反之则不稳定

内排序: 在排序整个过程中, 待排序的所有记录全部被放置在内存中.

外排序: 由于排序的记录个数太多, 不能同时放置在内存中, 整个排序过程需要在内外村之间多次数据交换才能进行

内排序

内排序可分为: 插入排序, 交换排序, 选择排序和归并排序四类

7种算法的各种性能指标的比较

从算法的件大喜来看, 7种算法可分为两类

• 简单算法: 冒泡, 简单选择, 直接插入
• 改进算法: 希尔, 堆, 归并, 快排

从最好情况来看, 如果待排序序列总是基本有序, 冒泡和直接插入排序快些, 反而不应该考虑4种复杂的改进算法

从最坏情况来看, 堆排序和归并排序有强过快速排序以及其他的简单排序

从时间复杂度来看, 堆排序和归并排序发挥稳定, 快排在较差的环境下会变得差强人意

从稳定性来看, 归并排序独占鳌头

从待排序记录的个数上来说, 待排序的个数n越小, 采用简单排序方法越适合. 反之, n越大, 采用改进排序方法越适合. 这就是为什么对快排优化时增加了一个阀值, 低于阀值时换做直接插入的原因

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