目录 start

  1. 排序算法
    1. 冒泡
    2. 插入
    3. 选择
    4. 归并
    5. 希尔
    6. 快速
    7. 基数
    8. 堆
    9. Tim

目录 end|2020-04-27 23:42|

排序算法

Github： Java 实现 | Python 实现

参考: 十大经典排序算法 Github: 十大经典排序算法

wikipedia 排序算法

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡 n^2 n n^2 1 In 稳定
插入 n^2 n n^2 1 In 稳定
选择 n^2 n^2 n^2 1 In \
希尔 n log n n log n n log n 1 In \
归并 n log n n log n n log n n Out 稳定
快速 n log n n log n n^2 log n In \
堆 n log n n log n n log n 1 In \
计数 n + k n + k n + k k Out 稳定
桶 n + k n + k n^2 n + k Out 稳定
基数 n * k n * k n * k n + k Out 稳定
  • n：数据规模
  • k：“桶"的个数
  • In-place：占用常数内存，不占用额外内存
  • Out-place：占用额外内存
  • 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

冒泡

步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
    • 这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

优缺点

  1. 优点：实现简单
  2. 缺点：性能略差

极端情况

  1. 最好：数据已经有序
  2. 最坏：数据全反序

优化策略

  1. 在每次遍历的时候加上一个检查， 判断是否已经有序，有序就直接退出排序

插入

步骤

  1. 首先将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
    • 随着算法执行有序序列逐渐替换掉未排序序列
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，实现无序向有序的转换
    • 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

优缺点

  1. 优点：实现简单
  2. 缺点：性能略差

极端情况

  1. 最好：数据已经有序
  2. 最坏：数据全反序

优化算法

  1. 拆半插入

选择

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

归并

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

希尔

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

快速

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

基数

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

堆

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法

Tim

步骤

优缺点

  1. 优点：
  2. 缺点：

极端情况

  1. 最好：
  2. 最坏：

优化算法