3分钟快速实现:9种经典排序算法的可视化

最近在某网站上看到一个视频,是关于排序算法的可视化的,看着挺有意思的,也特别喜感。

6分钟演示15种排序算法

附上源码链接:

(觉得不错,记得帮忙点个star哦)

下面具体讲解以下实现的思路,大概需要解决的问题如下:

一、如何表示数组

二、如何得到随机采样数组,数组有无重复数据

假设我希望数组长度是100,而且我希望数组的大小也是在[0,100)内,那么如何得到100个随机的整数呢?可以用random库。

示例代码:

importrandomdata=list(range(100))data=random.choices(data,k=100)print(data)[52,33,45,33,48,25,68,28,78,23,78,35,24,44,69,88,66,29,82,77,84,12,19,10,27,24,57,42,71,75,25,1,77,94,44,81,86,62,25,69,97,86,56,47,31,51,40,21,41,21,17,56,88,41,92,46,56,80,23,70,49,96,83,54,16,36,82,24,68,60,16,98,16,81,10,13,11,24,68,35,56,39,23,44,6,30,3,60,56,66,38,28,47,47,25,90,89,38,68,21]

但是以上代码有个问题,random.choices是对一个序列进行重复采样,得到的数组存在重复数据,那如果不希望存在重复数据,而是希望进行无重复采样,怎么办?

可以用random.sample函数,示例代码:

data=random.sample(data,k=100)print(data)[49,28,56,28,44,62,81,25,48,33,54,38,30,16,13,19,23,56,60,66,41,24,68,68,77,92,78,24,66,3,80,94,78,41,84,88,21,56,25,25,75,24,38,82,31,52,23,10,71,40,27,46,33,35,56,51,1,23,12,25,89,16,21,21,11,42,47,44,81,35,86,88,29,36,77,16,39,6,57,69,96,68,24,86,97,90,69,10,68,98,56,44,83,47,70,17,47,82,60,45]

这样就可以得到无重复采样数据了。

三、如何实现排序算法

算法种类较多,就不一一举例;再次就以希尔排序(ShellSort)为例讲讲:

尔排序的原理:希尔排序(ShellSort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

基础的插入法排序是两重循环,希尔排序是三重循环,最外面一重循环,控制增量gap,并逐步减少gap的值。二重循环从下标为gap的元素开始比较,依次逐个跨组处理。最后一重循环是对组内的元素进行插入法排序。这样进行排序的优点在于每次循环,整个序列的元素都将小元素的值逐步向前移动,数值比较大的值向后移动。

fromdataimportDataSeqdefShellSort(ds):assertisinstance(ds,DataSeq),"TypeError"Length=ds.lengthD=Length//2whileD>0:i=0whilei=1andds.data[j-D]>tmp:ds.SetVal(j,ds.data[j-D])j-=Dds.SetVal(j,tmp)i+=DD//=2if__name__=="__main__":ds=DataSeq(64)ds.Visualize()ds.StartTimer()ShellSort(ds)ds.StopTimer()ds.SetTimeInterval(0)ds.Visualize()

四、如何把数组可视化出来

有了随机数组初始化方法,再实现好排序函数,我们还差一步,就是把排序函数中每次移动数组后将数组可视化并输出。

对数组进行可视化,很容易想到Python的可视化工具matplotlib!但是在项目中我并没有用matplotlib,而是用了numpy+opencv。

为什么不用matplotlib?

因为在排序过程中,每次修改数组,都希望能够实时修改图片并输出,matplotlib确实很方便,但是matplotlib的效率实在是不高,而且每次修改数组前后的两幅图片其实是差不多的。如果用matplotlib,每次都是要重新绘制图片,非常耗时!!!

所以考虑自己生成图片,在每次修改数组后,只将图片中改动的那两列进行修改即可!这样就比用matplotlib每次重新绘制图片效率高得多!

数组中主要有两种操作,一种是对某个idx赋值,一种是交换某两个idx的值。

classDataSeq:WHITE=(255,255,255)RED=(0,0,255)BLACK=(0,0,0)YELLOW=(0,127,255)def__init__(self,Length,time_interval=1,sort_title="Figure",repeatition=False):passdefGetfigure(self):_bar_width=5figure=np.full((self.length*_bar_width,self.length*_bar_width,3),255,dtype=np.uint8)foriinrange(self.length):val=self.data[i]figure[-1-val*_bar_width:,i*_bar_width:i*_bar_width+_bar_width]=self.GetColor(val,self.length)self._bar_width=_bar_widthself.figure=figuredef_set_figure(self,idx,val):min_col=idx*self._bar_widthmax_col=min_col+self._bar_widthmin_row=-1-val*self._bar_widthself.figure[:,min_col:max_col]=self.WHITEself.figure[min_row:,min_col:max_col]=self.GetColor(val,self.length)defSetVal(self,idx,val):self.data[idx]=valself._set_figure(idx,val)self.Visualize((idx,))defSwap(self,idx1,idx2):self.data[idx1],self.data[idx2]=self.data[idx2],self.data[idx1]self._set_figure(idx1,self.data[idx1])self._set_figure(idx2,self.data[idx2])self.Visualize((idx1,idx2))

详细代码见github:

(就等你的小小star)其他的都没有什么了,有细节的问题可以在我的github下面留言勾搭。

最后附上一张效果图:

CTA核心技术及应用峰会

5月25-27日,由中国IT社区CSDN与数字经济人才发展中心联合主办的第一届CTA核心技术及应用峰会将在杭州国际博览中心隆重召开,峰会将围绕人工智能领域,邀请技术领航者,与开发者共同探讨机器学习和知识图谱的前沿研究及应用。

THE END
1.算法的基础概念,从入门到精通,教育,高等教育,好看视频算法的基础概念,从入门到精通 百度文库 53万粉丝 · 77万个视频百度文库官方账号 关注 接下来播放自动播放 02:01 顶梁柱这次是真的倒下了 和平精英 地铁逃生 顶梁柱倒下了 关唱地铁逃生 5689次播放 · 108次点赞 15:23 中国父亲来老挝参加乔迁宴!把厨师也带来了,让村民尝中国席面! 小陈的老挝媳妇 27万次https://haokan.baidu.com/v?pd=wisenatural&vid=15449967741319345145
2.腾讯视频网络上疯传的一道高智商数学题,你能算出来等于多少吗腾讯视频 看全集高清完整版 小程序免广告 打开APP 再看一遍 更多热门短视频 小程序免广告 APP看全集 请选择以下方式打开并播放 继续使用浏览器 腾讯视频 小程序免广告 快捷免安装,限时免广告观看 打开 腾讯视频 APP 畅享完整播放体验 打开 https://m.v.qq.com/z/msite/play-short/index.html?qqVersion=0&vid=w0843zduv7k
3.十大经典算法之动图演示前面好奇心已经带大家从冒泡排序开始,一直到基数排序,从头过了一遍,那么这里归纳一下,将十个经典算法的演示图都放出来,供大家对比参考学习。 每张图都会附带详细解说链接,有需要的同学可以点击详细了解学习。 冒泡排序 Python 实现经典算法之冒泡排序 选择排序 https://www.360doc.cn/article/40020072_1120709857.html
4.十大经典排序算法动画演示AlgorithmMan,一套免费的算法演示神器,附带GitHub开源下载地址。 1、Sorting Algorithms Animations 2、算法的分类 3、时间复杂度 算法 1、冒泡排序 它重复地访问要排序的元素列,一次比较两个相邻的元素,如果他们的顺序不符合预期就把他们交换过来。访问元素的工作是重复地进行直到没有相邻元素需要交换时为止。 https://www.jianshu.com/p/e9cfc2cc869c
5.Python数据结构之十大经典排序算法一文通关python今天整理一下十大经典排序算法。 1、冒泡排序 ——越小的元素会经由交换慢慢“浮”到数列的顶端 算法演示 算法步骤 比较相邻的元素。如果第一个比第二个大,就交换它们两个; 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数; https://www.jb51.net/article/225443.htm
6.基于VisualC++的数据结构经典算法的演示系统(2014年)资源本文利用Visual C++ 6.0开发平台的可视化界面以及其中的MFC环境的优点,设计并建立了一个基于C++的数据结构的经典算法的演示系统,这使得学生加深了算法的理解,也提高了学生的学习兴趣,达到了更好的授课效果。 资源推荐 资源评论 C++数据结构算法演示系统(论文).pdf https://download.csdn.net/download/weixin_38567873/19631009
7.GitHubJourWon/sort查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码https://github.com/JourWon/sort-algorithm
8.十大经典排序算法动画,看我就够了!Tip为了演示更加清楚,本文中所有的动画都放慢了速度,因此GIF大小对比之前会有所增大,图片加载速度会变慢,如果你想获取所有的超清动画,在公主号 五分钟学算法 回复github可获得全部资料。 在前面的章节中详细的讲解分析了十大经典排序算法,本文将进行一个大总结同时分析它们的时间复杂度与稳定性。 https://www.imooc.com/article/266110
9.算法学习笔记51CTO博客《数学建模十大经典算法》 《数据挖掘领域十大经典算法》 《十道海量数据处理面试题》 《数字图像处理领域的二十四个经典算法》 《精选微软等公司经典的算法面试100题》 The-Art-Of-Programming-By-July 微软面试100题 程序员编程艺术 基本算法演示 http://sjjg.js.zwu.edu.cn/SFXX/sf1/sfys.html https://blog.51cto.com/u_15310381/3229422
10.KMeans算法动画演示分析文章见:http://blog.csdn.net/gugugujiawei/article/details/45578547 上传者:gugugujiawei时间:2015-05-08 KMeans算法java代码 KMeans算法是机器学习的经典算法,该文档实现了KMeans算法,文档中的数据是为了实现算法随机构造的。 上传者:u010619558时间:2018-01-23https://www.iteye.com/resource/qq_36382679-12921697
11.龙桂鲁教授团队完成量子梯度算法原理演示2021年 龙桂鲁教授团队完成量子梯度算法原理演示 算法、数据和算力是人工智能的三个要素。随着人类步入大数据时代,数据量呈现井喷式增长。要最快的到达山顶目标的爬山路线,是最陡的路线,梯度方向就是朝着目标最陡的方向。在优化算法中,梯度算法就是沿着目标函数的梯度方向,快速寻找极值的算法。梯度算法被广泛应用在机器https://www.phys.tsinghua.edu.cn/info/1129/4541.htm
12.算法精粹:经典计算机科学问题的Python实现本书是一本面向中高级程序员的算法教程,借助Python语言,用经典的算法、编码技术和原理来求解计算机科学的一些经典问题。全书共9章,不仅介绍了递归、结果缓存和位操作等基本编程组件,还讲述了常见的搜索算法、常见的图算法、神经网络、遗传算法、k均值聚类算法、对抗搜索算法等,运用了类型提示等Python高级特性,并通过各级https://www.epubit.com/bookDetails?id=UB71fac289a9240
13.量子计算机美国的洛斯阿拉莫斯和麻省理工学院、IBM、和斯坦福大学、武汉物理教学所、清华大学四个研究组已实现7个量子比特量子算法演示。 20世纪60年代至70年代,人们发现能耗会导致计算机中的芯片发热,极大地影响了芯片的集成度,从而限制了计算机的运行速度。研究发现,能耗来源于计算过程中的不可逆操作。那么,是否计算过程必须要用https://baike.sogou.com/v323052.htm
14.生活中的算法教案.doc导入新课:通过展示一些生活中的问题,如如何快速找出100元钞票、如何将一堆鞋子快速排序等,引导学生思考如何用算法解决这些问题。 2. 讲解概念:介绍常见的算法概念,如排序、查找、计数等,并解释其原理和用途。 3. 实例分析:通过分析实际生活中的问题,让学生了解如何将算法应用于解决这些问题。例如,通过演示快速排序https://m.book118.com/html/2023/1122/5233332323011012.shtm