各类排序算法对比

在此之前大家可以看下这个浅谈算法的BBC先回顾下:

( bilibili地址 ，这里不引用bilibili因为bilibili比较模糊)

BBC讨论概况:

• 通过一个小游戏讲述了算法在生活中的作用
• 从1964年诞生的冒泡 排序算法 开始介绍 排序 的算法
• 归并排序(拆分区域，分别合并有序的区域(由于有序对区域头分别对比即可)，展示了只要数据一多归并排序对比冒泡排序的优势就展示出来了
• 大概介绍了世界上有大约20种的排序算法
• 最短路径问题: 通过实验，展示了蜜蜂在寻找最短路径上的天赋，不过蜜蜂并不是找到最短的路径，而是对于其而言接近最短路径，换言之是足够短的路径

I. 各类排序应用场景对比

世界上有大于20种的排序排序算法，比如网络上就有 23种排序算法比较 的视频。

再比如 该圆盘排序对比 给了很多有趣的排序，下面对其中提到效率对比:

• Double Selection Sort
• Gravity Sort
• Counting Sort
• Radix LSD Sort(Base 4)
• Radix LSD In-Place Sort (Base 10)
• Radix MSD Sort(Base 4)
• Time Sort(mul 4) + Insertion Sort

不过今天我们主要谈到常见的9种排序。对于排序而言其效率无法进行纯粹的对比，因为其涉及的纬度众多，比如数据量，原本的混乱情况，读写速度、处理速度等都会对其影响。

不过我们今天就对于混乱情况借助下面这个很有意思的视频，对其效率进行排序下:

II. 各类排序详细分析

1. 选择排序 - Selection sort

选择排序-维基

原理

选择排序为众多排序里面最简单暴力的方案，简而言之就是每次找到最小的放到前面: 遍历长度为n的整个数组，第i次遍历，找到最小的（或最大）与i所在值进行替换。

每次交换情况:

5  6  1  8  2  4
↑     ↑
└─────┘
[1]  6  5  8  2  4
     ↑        ↑
     └────────┘
[1, 2]  5  8  6  4
        ↑        ↑
        └────────┘
[1, 2, 4]  8  6  5
           ↑     ↑
           └─────┘
[1, 2, 4, 5]  6  8
[1, 2, 4, 5, 6]  8
[1, 2, 4, 5, 6, 8]

效率分析

• 交换操作次数: [0, n-1] -> $O(n)$
• 比较次数: (n-1) + (n-2) + … + 1 = $n\frac{(n-1)}{2} -> $O(n^2)$
• 最好情况: 已经有序，交换0次
• 最坏情况: 交换$n-1$次
• 逆序交换: 交换$\frac{n}{2}$次
• 稳定性: 不稳定排序(由于每次交换前后顺序就被破坏)
• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(1)$

横向对比

• 交换次数比 冒泡排序 少很多 : 比冒泡排序快，由于交换所需CPU时间 > 比较所需CPU时间
• 当记录占用字节数较多时，通常比 插入排序 执行速度快些。

2. 插入排序 - Insert sort

插入排序-维基 , 在几乎排列好的队列中效率最高，因为在有序的队列中，其完全不用赋值，只需要进行$n-1$次比较即完成排序。

原理

插入排序的原理很想扑克牌抓牌，每次抓牌都是从桌面上的牌抓起插入已经排好序的手中的牌中: 往已经有序的数据序列中插入一个数，使得插入完成后依然有序。

每次交换情况:

[5]  6  1  8  2  4
  ↑  │
  └──┘
[5, 6]  1  8  2  4
↑       │
└───────┘
[1, 5, 6]  8  2  4
        ↑  │
        └──┘
[1, 5, 6, 8]  2  4
   ↑          │
   └──────────┘
[1, 2, 5, 6, 8]  4
         ↑       │
         └───────┘
[1, 2, 4, 5, 6, 8]

效率分析

• 稳定性: 稳定排序
• 比较操作最好情况: 源数据有序，只需要$n-1$次
• 比较操作最坏情况: 源数据逆序，需要$\frac{1}{2}n(n-1)$次
• 赋值次数: $(比较操作次数) - (n-1)$ 因为$n-1$次循环中，每一次循环的比较都比赋值多一个，多在最后那次比较并不带来赋值
• 时间复杂度: $O(n^2)$ (最坏: $O(n^2)$; 最优: $O(n)$)
• 空间复杂度: 辅助空间$O(1)$用于

已有应用场景

• 由于其时间复杂度的缘故，不适合用于数据量较大的数据(如量级大于千)
• 在STL的sort算法和stdlib的qsort算法中被作为快速排序的补充，用于少量元素的排序(8个或以下)

3. 冒泡排序 – Bubble sort

原理

从后往前分别两两对比，

每次交换情况:

5  6  1  8  2  4
         ↑  ↑
         └──┘
5  6  1  2  8  4
   ↑  ↑
   └──┘
5  1  6  2  8  4
↑  ↑
└──┘
[1]  5  6  2  8  4
              ↑  ↑
              └──┘
[1]  5  6  2  8  4
              ↑  ↑
              └──┘
[1]  5  6  2  4  8
        ↑  ↑
        └──┘
[1]  5  2  6  4  8
     ↑  ↑
     └──┘
[1, 2]  5  6  4  8
           ↑  ↑
           └──┘
[1, 2]  5  4  6  8
        ↑  ↑
        └──┘
[1, 2, 4]  5  6  8
[1, 2, 4, 5]  6  8
[1, 2, 4, 5, 6]  8
[1, 2, 4, 5, 6, 8]