各类排序算法对比

栏目: 编程工具 · 发布时间: 5年前

内容简介:在此之前大家可以看下这个浅谈算法的BBC先回顾下:(BBC讨论概况:

在此之前大家可以看下这个浅谈算法的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种排序。对于排序而言其效率无法进行纯粹的对比,因为其涉及的纬度众多,比如数据量,原本的混乱情况,读写速度、处理速度等都会对其影响。

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

效率排名 完全逆序 乱序 部分相同 几乎有序
1 快速排序(Quick) 快速排序(Quick) 快速排序(Quick) 插入排序(Insertion)
2 希尔排序(Shell) 希尔排序(Shell) 希尔排序(Shell) 鸡尾酒排序(Cocktail)
3 归并排序(Merge) 归并排序(Merge) 归并排序(Merge) 快速排序(Quick)
4 堆排序(Heap) 堆排序(Heap) 堆排序(Heap) 希尔排序(Shell)
5 梳排序(Comb) 梳排序(Comb) 梳排序(Comb) 归并排序(Merge)
6 选择排序(Selection) 插入排序(Insertion) 插入排序(Insertion) 梳排序(Comb)
7 插入排序(Insertion) 选择排序(Selection) 选择排序(Selection) 堆排序(Heap)
8 冒泡排序(Bubble) 鸡尾酒排序(Cocktail) 鸡尾酒排序(Cocktail) 冒泡排序(Bubble)
9 鸡尾酒排序(Cocktail) 冒泡排序(Bubble) 冒泡排序(Bubble) 选择排序(Selection)

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]

以上所述就是小编给大家介绍的《各类排序算法对比》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

注意力商人

注意力商人

吳修銘 / 黃庭敏 / 天下雜誌 / 2018-4-2 / NT$650

電子郵件,免費!照片分享,無上限! 你是否想過,隨手可得的免費內容、便利的免費服務,到底都是誰在付費? 如果商品免費,那你就不是消費者,而是商品! 你我可能都不知不覺地把自己賣給了注意力商人! 「『媒體轉型、網路演化與資訊浪潮」此一主題最具洞見的作者。』──黃哲斌(資深媒體人) 「這是少有的關注產業發展的傳播史,對現在或未來的『注意力產業』」中人來說,不可不讀。」──......一起来看看 《注意力商人》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

SHA 加密
SHA 加密

SHA 加密工具