分享好友 最新动态首页 最新动态分类 切换频道
十大经典排序算法及比较与分析 ( 动画演示 ) ( 可视化工具 )
2024-12-29 23:43

可视化工具及动画展示：旧金山大学 (usfca)|数据结构可视化工具

排序算法概念及描述：1.0 十大经典排序算法（文章部分内容引用自改文章）
参考：邓俊辉 的数据结构
本文未对排序算法概念进行详细说明，只是提供已经验证过的代码及对算法核心进行简要说明
常用八种排序算法： 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序

·
全部代码（github） C#版本

0X00 前言

排序算法是《数据结构与算法》中最基本的算法之一。

线性对数阶 (O(nlog2n)) （ log2n 是以2为底数的n的对数）排序： 快速排序、堆排序和归并排序；

O(n1+§)) 排序 ( § 是介于 0 和 1 之间的常数 )： 希尔排序

线性阶 (O(n)) 排序： 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

  • n：数据规模
  • k："桶"的个数
  • In-place：占用常数内存，不占用额外内存
  • Out-place：占用额外内存
  • 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

0X01 冒泡排序(起泡排序)

可视化工具及动画演示

 

0X02 选择排序(直接选择排序)
 

 
 
可视化工具及动画演示
 

 

 

0X03 插入排序(直接插入排序)
 

 
 
适合少量元素排序
 可视化工具及动画演示
 

 

 

0X04 希尔排序
 

 
 
基于插入排序
 参考学习：https://baijiahao.baidu.com/s?id=1644158198885715432&wfr=spider&for=pc
 可视化工具及动画演示
 

 

 

0X05 归并排序
 

 
 
可视化工具及动画演示
 

 

 

0X06 快速排序
 

 
 
可视化工具及动画演示
 

 

 

0X07 堆排序
 

 
 
可视化工具及动画演示
 时间复杂度参考：堆排序的时间复杂度分析
 

 

 

0X08 计数排序
 

 
 
可视化工具及动画演示
 

 

 

0X09 桶排序
 

 
 
可视化工具及动画演示
 

 

 

0X10 基数排序
 

 
 
可视化工具及动画演示
 

 

 

0X11 全部代码（C#）
 

 
 
全部代码（github）
 

 

0X12 排序算法耗时测试
 

 
 
全部代码（github）
 测试环境：（.Net4.6.1,win10）
 

 

 
 
 
  
数组长度50，数组元素(0–1000).
 BubbleSort总共花费0.3393ms.
 BubbleSort_E总共花费0.1743ms.
 SelectionSort总共花费0.1832ms.
 InsertionSort总共花费0.1752ms.
 InsertionSort_E总共花费0.1461ms.
 ShellSort总共花费0.2367ms.
 MergeSort总共花费0.4245ms.
 MergeSort_E总共花费0.4201ms.
 QuickSort总共花费0.3644ms.
 QuickSort_V总共花费0.4239ms.
 HeapSort总共花费0.2615ms.
 CountingSort总共花费0.2181ms.
 BucketSort总共花费3.492ms.
 RadixSort总共花费0.3766ms.
 
 
 
 
 
  
数组长度500，数组元素(0–1000).
 BubbleSort总共花费1.4969ms.
 BubbleSort_E总共花费1.7962ms.
 SelectionSort总共花费0.4618ms.
 InsertionSort总共花费1.2992ms.
 InsertionSort_E总共花费0.2969ms.
 ShellSort总共花费0.4273ms.
 MergeSort总共花费0.4269ms.
 MergeSort_E总共花费0.2781ms.
 QuickSort总共花费0.2806ms.
 QuickSort_V总共花费0.3587ms.
 HeapSort总共花费0.3837ms.
 CountingSort总共花费0.2465ms.
 BucketSort总共花费1.3181ms.
 RadixSort总共花费0.2294ms.
 
 
 
 
 
  
数组长度1000，数组元素(0–1000).
 BubbleSort总共花费4.9505ms.
 BubbleSort_E总共花费4.669ms.
 SelectionSort总共花费1.2467ms.
 InsertionSort总共花费3.395ms.
 InsertionSort_E总共花费1.3513ms.
 ShellSort总共花费1.3414ms.
 MergeSort总共花费0.5231ms.
 MergeSort_E总共花费0.4844ms.
 QuickSort总共花费0.3366ms.
 QuickSort_V总共花费0.3937ms.
 HeapSort总共花费0.4446ms.
 CountingSort总共花费0.2668ms.
 BucketSort总共花费2.6375ms.
 RadixSort总共花费0.5076ms.
 
 
 
 
 
  
数组长度5000，数组元素(0–1000).
 BubbleSort总共花费134.6438ms.
 BubbleSort_E总共花费141.5785ms.
 SelectionSort总共花费32.566ms.
 InsertionSort总共花费82.5932ms.
 InsertionSort_E总共花费17.178ms.
 ShellSort总共花费22.8029ms.
 MergeSort总共花费1.0649ms.
 MergeSort_E总共花费0.7582ms.
 QuickSort总共花费0.7838ms.
 QuickSort_V总共花费0.8333ms.
 HeapSort总共花费1.5709ms.
 CountingSort总共花费0.2693ms.
 BucketSort总共花费1.7872ms.
 RadixSort总共花费0.4634ms.
 
 
 
 
 
  
数组长度10000，数组元素(0–1000).
 BubbleSort总共花费556.6481ms.
 BubbleSort_E总共花费528.7346ms.
 SelectionSort总共花费116.9845ms.
 InsertionSort总共花费306.6125ms.
 InsertionSort_E总共花费68.4407ms.
 ShellSort总共花费88.4968ms.
 MergeSort总共花费1.8969ms.
 MergeSort_E总共花费1.3673ms.
 QuickSort总共花费1.4713ms.
 QuickSort_V总共花费1.4491ms.
 HeapSort总共花费3.3177ms.
 CountingSort总共花费0.3216ms.
 BucketSort总共花费2.9245ms.
 RadixSort总共花费0.7497ms.
 
 
 
 
 
  
数组长度30000，数组元素(0–1000).
 BubbleSort总共花费4702.0921ms.
 BubbleSort_E总共花费4660.4316ms.
 SelectionSort总共花费952.3607ms.
 InsertionSort总共花费2763.3749ms.
 InsertionSort_E总共花费610.9831ms.
 ShellSort总共花费777.4363ms.
 MergeSort总共花费5.3142ms.
 MergeSort_E总共花费3.806ms.
 QuickSort总共花费4.2744ms.
 QuickSort_V总共花费4.4204ms.
 HeapSort总共花费10.0902ms.
 CountingSort总共花费0.5658ms.
 BucketSort总共花费18.1321ms.
 RadixSort总共花费1.8263ms.
 
 
 
 
 
  
数组长度100000，数组元素(0–1000).
 BubbleSort总共花费52096.3052ms.
 BubbleSort_E总共花费52299.5447ms.
 SelectionSort总共花费10567.5827ms.
 InsertionSort总共花费30973.0239ms.
 InsertionSort_E总共花费6888.8287ms.
 ShellSort总共花费8548.7395ms.
 MergeSort总共花费17.985ms.
 MergeSort_E总共花费13.3151ms.
 QuickSort总共花费19.1267ms.
 QuickSort_V总共花费18.6859ms.
 HeapSort总共花费36.055ms.
 CountingSort总共花费1.3793ms.
 BucketSort总共花费195.1004ms.
 RadixSort总共花费6.1907ms.
 
 
 

 

通过测试数据得出：
 

  • 没有空间开销的算法中（不考虑原始数据局部有序） 小数据量（<500） 直接插入排序最优(E版本) ；大数据量(>500) 快速排序最优（递归版本，不考虑递归开销）。
  • 有空间开销的算法中 (不考虑空间开销大小，大数据量>1000）基数排序和计数排序最优，其次是归并排序（E版本非递归）。
 

 
 
桶排序的耗时不是最优的，这里的桶排序没有设置桶的size，所以桶排序耗时不考虑。
 如果有出入或者错误望各位留言指正
 

 

0X13 十大算法比较与分析
 

  • 这里是参考其他文章的结论进行了罗列，我自己的测试结论参考上一节（ 0X13 ）节
 

 
 
  •  
    直接插入排序 是对冒泡排序的改进，比冒泡排序快，但是只适用于数据量较小(1000 ) 的排序
     
  •  
    希尔排序 比较简单，适用于小数据量（5000以下）的排序，比直接插入排序快、冒泡排序快，因此，希尔排序适用于小数据量的、排序速度要求不高的排序。
     
  •  
    直接选择排序 和冒泡排序算法一样，适用于n值较小的场合，而且是排序算法发展的初级阶段，在实际应用中采用的几率较小。
     
  •  
    堆排序 比较适用于数据量达到百万及其以上的排序，在这种情况下，使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。
     
  •  
    冒泡排序 是最慢的排序算法，是排序算法发展的初级阶段，实际应用中采用该算法的几率比较小。
     
  •  
    快速排序 是递归的、速度最快的排序算法，但是在内存有限的情况下不是一个好的选择;而且，对于基本有序的数据序列排序，快速排序反而变得比较慢。
     
  •  
    归并排序 比堆排序要快，但是需要的存储空间增加一倍。
     
  •  
    基数排序 适用于规模n值很大的场合，但是只适用于整数的排序，如果对浮点数进行基数排序，则必须明确浮点数的存储格式，然后通过某种方式将其映射到整数上，最后再映射回去，过程复杂。
     
 
 
摘自常用排序算法比较与分析
 

 

 

 
 
冒泡排序：
 效率太低，通过冒泡可以掌握swap。
 
 
选择排序：
 效率较低，但经常使用它内部的循环方式来找最大值和最小值。
 
 
插入排序：
 虽然平均效率低，但在序列基本有序时，它很快，所以也有其适用范围。
 
 
希尔排序：
 是插入排序的改良，对空间思维训练有帮助。
 
 
快速排序：
 快排是软件工业中最常见的常规排序法，其双向指针扫描和分区算法是核心。
 
 
往往用于解决类似问题，特别地partition算法用来划分不同性质的元素，
 partition->selectK,也用于著名的top问题
 O(NlgN)，但是如果主元不是中位数的话，特别地如果每次主元都在数组区间的一侧，复杂度将退化为N²
 工业优化：三点取中法，绝对中值法，小数据量用插入排序
 快排重视子问题拆分
 
 
归并排序：
 空间换时间——逆序对数，
 
 
归并重视子问题的解的合并
 
 
堆排序：
 用到了二叉堆数据结构，是继续掌握树结构的起手式。=插排+二分查找
 
 
上面7种都是基于比较的排序，可证明它们在元素随机顺序情况下最好是NlgN的，用决策树证明
 
 
下面三个是非比较排序，在特定情况下会比基于比较的排序要快：
 
 
计数排序：
 可以说是最快的：O(N+k),k=maxOf(sourceArr)，用它来解决问题时必须注意如果序列中的值分布非常广（最大值很大，元素分布很稀疏），
 空间将会浪费很多
 所以计数排序的适用范围是：序列的关键字比较集中，已知边界，且边界较小
 
 
桶排序：
 先分桶，再用其他排序方法对桶内元素排序，按桶的编号依次检出。（分配-收集）
 用它解决问题必须注意序列的值是否均匀地分布在桶中。
 如果不均匀，那么个别桶中的元素会远多于其他桶，桶内排序用比较排序，极端情况下，全部元素在一个桶内，还是会退化成NlgN。
 
 
其时间复杂度是：时间复杂度： O(N+C)，其中C=N(logN-logM)，约等于NlgN
 N是元素个数，M是桶的个数。
 
 
基数排序：
 kN级别（k是最大数的位数）是整数数值型排序里面又快又稳的，无论元素分布如何，
 只开辟固定的辅助空间（10个桶）
 
 
对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，对十进制整数来说，基数排序更好用。
 
 
摘自10种排序算法的对比分析
 

 

0X14 数据结构可视化工具
 

 
 
可视化工具及动画展示地址：旧金山大学|数据结构可视化
 

 
 
 
 
 

点击向后跳就然后点上面的某个排序按钮就可以重新播放啦








最新文章





AIGC、AGI、ChatGPT：揭秘人工智能大模型的变革与创新

随着科技的不断发展，人工智能(AI)已经深入到我们生活的方方面面，从语音助手到自动驾驶汽车，再到智能家居，AI的影子无处不在。而在近年来，AIGC、AGI和ChatGPT等人工智能大模型的出现，更是引领了一



AI智能回访

AI应用一：智能IVR说需求便可直达业务，无需按键极致体检。智能IVR，客户呼入后无需按键说出需求就可以直接进入相应业务节点，如自助查询、自助办理、转到相应业务队列等。 智能IVR系统能够快速、准确、完整地识别客户语音，通过自然语言理



chrome.devtools.panels

模块用以整合您的扩展到开发者工具窗口中：创建您自己的面板，访问已存在的面板和添加侧边栏。访问 DevTools 接口介绍 了解使用开发人员工具 API 的使用简介。每个扩展面板和侧边栏都被展示为一个独立的HTML页面。展现在开发者工具窗口的所



APP原生webview实现H5微信支付

公司新接了一个需求，要求把现有的小程序代码转化为H5，这能难的倒我嘛，在上个版本已经把原生小程序改造成Taro框架的我，五分钟就把dist包打出来甩给了产品，任务完成。“不错不错，客户还要求使用微信H5支付”，我还是丝毫不慌，之前也是



2025年SEO趋势揭秘：AI如何重塑搜索引擎格局？

在瞬息万变的数字营销世界，SEO（搜索引擎优化）一直是推动企业在线表现的重要力量。然而，进入2025年，SEO的形态正在经历前所未有的变革，尤其是随着人工智能（AI）的迅速发展，对搜索引擎及其排名机制的影响愈发明显。这一切都在推动着企



AI大模型王炸辅助-RAG到底有什么能耐？一文揭秘检索增强生成技术（RAG）的几种工作类型与其背后的奇思妙想

今天这篇文章就来为大家介绍了检索增强生成(RAG)技术的几种基本工作类型，以及RAG中用到的高级的技术，来看看科学家们优化大模型，都是用了什么样的好点子 RAG的几种工作类型提示增强 Query-based RAG Query-based RAG(



​2024上海网上年货节正式启动！2024-01-18来源：市商务委字号：大中小




Buy Valve Complete PackBUNDLE(？)

For over two decades, Counter-Strike has offered an elite competitive experience, one shaped by millions of players from across the globe. And now the next chapter in the CS story is about to begin. This is Counter-Strike



AI墓地，和738个死去的AI项目

一个并不意外的故事。作者：Jessica来源：硅星人Pro（ID：Si-Planet）这份死亡名单上有738个名字。其中不乏一些曾经的明星AI项目，例如OpenAI推出的AI语音识别产品Whisper.ai，Stable Diffusion的知名套壳网站FreewayML、StockAI，以及曾被



C语言 史上最详细快速排序图解，让小白也能轻松理解

快速排序可以看作是冒泡排序的一种升级版，优点就是快速，但是稳定性差。 因为是史上最详细快速排序，所以我写的非常细~~基本每一句代码都解释+图解到位了，需要耐心浏览。 快速排序的功能概括就是在数组中选






相关文章








推荐文章





Facebook查看广告系列、广告组或广告投放状态




AI智能获客系统骗局，保持警惕，科学应对




AI换衣服软件(FacePlay)




excel表格怎样设置多行多列数据内容排序-英雄云拓展知识分享




ai+模型选择+过拟合和欠拟合




ai智能扩图怎么做出来的？AI绘图助手一键智能扩图




APA Citation Style(APA 论文引用规范).doc




1. 用第三方 Recovery 刷入 GApps




gmod开服多少钱




2024中国大学QS排名 2024年QS中国大学排名完整名单（中国大学排名qs）











发表评论

0评