分享好友 最新动态首页 最新动态分类 切换频道
十大经典排序算法及比较与分析 ( 动画演示 ) ( 可视化工具 )
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 数据结构可视化工具
 

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

 
 
 
 
 

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








最新文章





beamer插入参考文献并引用（BibTex）

1.可以在要引用的文献页面点击Citation2.导出Citation格式为BibTex，将字符串复制下来。 3.在latex中新建文件，并把字符串粘贴进去，这里可以修改大括号内第一个逗号之前的部分，即红框内的部分（该部分即为文档中要引用的简称），可以修



AI客服系统：智能与人工的界限与融合

在数字化时代，客户服务作为企业与消费者之间的桥梁，其重要性不言而喻。随着人工智能技术的飞速发展，AI客服系统逐渐成为企业提升服务效率、优化客户体验的重要工具。然而，AI智能客服与人工客服之间究竟存在哪些区别？它们各自的优势与局



AI写广告语生成器：一键打造吸睛创意标题与内容

在数字化时代广告营销已成为企业竞争的关键战场之一。怎么样在这个信息爆炸的时代，让广告语独具匠心，吸引消费者的眼球，成为广告创作者们不断追求的目标。如今，技术的快速发展为广告创作带来了新的可能。本文将为您介绍一款写广告语生成



ai聊天机器人工具分享

随着人工智能技术的快速发展，聊天机器人已经成为了现代生活不可或缺的一部分。在今天的文章中，我们将分享一些AI聊天机器人工具，帮助你轻松实现智能对话。1.聪明灵犀电脑端该软件是一款基于人工智能技术的聊天软件。其内置的AI聊天功能可



Cluster - 基本概念

　　更详细的说，集群（一组协同工作的计算机）是充分利用计算资源的一个重要概念，因为它能够将工作负载从一个超载的系统（或节点）迁移到集群中的另一个系统上。其处理能力是与专用计算机(小型机,大



B端走查神器，快用起来吧

什么是界面走查在整个研发环节中，由于UI需要对上线的界面效果负责，所以研发线会有一个环节就是UI验收。就是在我们输出效果图和切图文件给前端后，前端根据我们的效果图进行代码编写，出来之后的HTML效果UI设计师需要进行验收。 虽然走查



AI智能应答机器人

一、概述AI智能应答机器人是一种能够通过人工智能技术，模拟人类智能进行对话和回答问题的机器人系统。它能够根据用户的提问，识别问题意图，快速准确地给出答案，大大提高了用户体验。AI智能应答机器人在各个行业中都具有广泛的应用前景。



ChatGPT 竟然开始讨要小费！人工智能离“勒索”人类还远吗？

原创 叶拾 科普中国在很多人眼里，人工智能是铁面无情的绝对理性化身。在算法驱动之下，它只会依照数学模型，产出人们想要的结果。除此之外，任何人类世界的糖衣炮弹、人际关系、各种诱惑，似乎都不应该影响它的表现。尽管拿不到真实的钱，



Download Google Chrome (32bit) 114.0.5735.134 for windows

Google Chrome is the most popular web browser on the market. It provides an easy-to-use and clean interface, reliable connections across devices, and a huge library of extensions. Its address bar is integrated with the Goo



51cms网站管理系统 v1.2.04

51cms网站管理系统是一款基于5ucms进行开发的内容管理系统。在经典的5ucms1.2版上修复了已知bug，并且更换了后台编辑器为ueditor。系统功能：1. 支持 ACCESS/MSSQL 数据库2. 支持动态浏览, Rewrite 模拟静态,生成静态页面,栏目动态+文章静






相关文章








推荐文章





AI换衣服软件(FacePlay)




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




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




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




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




1. 用第三方 Recovery 刷入 GApps




gmod开服多少钱




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




Android免杀小结




7788.com的百度排名情况











发表评论

0评