在前面的章节中详细的讲解分析了十大经典排序算法,本文将进行一个大总结同时分析它们的时间复杂度与稳定性。
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括:
稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
Tip 为了演示更加清楚,本文中所有的动画都放慢了速度,因此 GIF 大小对比之前会有所增大,图片加载速度会变慢,如果你想获取所有的超清动画,在公众号 五分钟学算法 回复 v2ex 可获得资料。
修正堆排序:
1
singlepig 2018-12-03 09:22:48 +08:00 1
楼主,7 堆排序和 6 的图是一样的
|
2
CoderOnePolo OP @singlepig 不好意思,上传错了
|
3
RyougiShiki 2018-12-03 09:31:22 +08:00 1
不错。编程领域需要设计,图明白多了。
|
4
CoderOnePolo OP @RyougiShiki 感谢肯定。也是因为之前学这个的时候太抽象了,感觉还是具体化就好理解了。
|
5
zxgfy12 2018-12-03 09:52:44 +08:00 1
这个很不错,特别是给入门的看。
话说这种动图,是用什么工具来做呢? |
6
richzhu 2018-12-03 09:55:07 +08:00
我前几天下载这个 APP 啦,哈哈哈~
|
7
mogami95 2018-12-03 09:58:16 +08:00 1
漂亮!
|
8
thfurior 2018-12-03 09:59:57 +08:00 1
不错,很清楚
|
9
jingyulong 2018-12-03 10:01:46 +08:00
从初学者的角度来写,不错的👍
|
10
CoderOnePolo OP @zxgfy12 都是自己用 PPT 做的,做的目的就是给初学者入门用的,希望能更好的理解。
|
11
CoderOnePolo OP @richzhu 是哪个 APP,我下载下来学习参考一下^_^
|
12
CoderOnePolo OP |
13
richzhu 2018-12-03 10:11:47 +08:00 1
@CoderOnePolo 苹果商店搜 “算法动画图解” 😀
|
14
CoderOnePolo OP @richzhu 收到,感谢!!!
|
15
vanishcode 2018-12-03 10:20:05 +08:00 via Android 1
楼主这个也挺好的。我之前学数据结构的时候用的 visualgo https://visualgo.net/zh
|
16
trait 2018-12-03 10:21:22 +08:00 1
楼主画个 timsort 吧,算是比较快的,好多语言的内置算法
|
17
ilunny 2018-12-03 10:26:58 +08:00 via Android
为什么冒泡排序最好情况是 O(n)
|
18
IdJoel 2018-12-03 11:27:01 +08:00 1
非常棒 感谢
|
19
CoderOnePolo OP |
20
hxz6688 2018-12-03 11:52:41 +08:00 1
感觉不错的
|
21
daweii 2018-12-03 11:55:49 +08:00 via iPhone 1
我的流量。。。
|
22
CoderOnePolo OP |
24
KingHL 2018-12-03 13:28:09 +08:00
赞一个
|
25
Mexion 2018-12-03 13:28:50 +08:00
先马克
|
26
jevirs 2018-12-03 13:36:09 +08:00
内容不错哦,附上代码印象更加深刻
|
27
CoderOnePolo OP @jevirs 在公众号系列里每一个排序动画都配上了几种语言的代码实现,可以关注看看🤔
|
28
loading 2018-12-03 14:06:19 +08:00 via Android 1
谷歌市场的算法动画的 app 是楼主的?
我设置三大金刚键后,底下按钮被挡。 |
29
CoderOnePolo OP @loading 不是,我还没做过类似的 APP
|
30
anonymous256 2018-12-03 14:25:25 +08:00 via Android
有小地方想要较真一下。
我们说一个算法的时间复杂度是一个关于问题规模的函数,大 O 的表示法已经是它最坏的情况(忽略系数)。如果要准确的计算一个算法再最好 /平均 /最坏的表现,应该用函数表示,不应该直接用 O 符号。参考算法导论的 T(n)表示法。 |
31
anonymous256 2018-12-03 14:28:08 +08:00 via Android 1
感觉每个图做成一个专题,旁边附上伪码(pseudocode),下面写上该算法的各种语言实现方式。一定很受学习者欢迎~
|
32
CoderOnePolo OP @anonymous256 目前每个图已经做成一个专题,这十个经典排序算法都用几种语言实现了,并且还配了伪码动画思路。文章在公众号里面可以看到^_^
|
33
zwh2698 2018-12-03 15:49:32 +08:00 via Android 1
赞👍
|
34
hei1000 2018-12-03 16:12:10 +08:00
不写成文章吗,这个不好放到 pocket 里面去啊
|
35
stebest 2018-12-03 17:17:16 +08:00 1
归并排序实际上有两种方式,时间复杂度一致。但比如在对于处理链表排序时候,两种方式的空间复杂度分别为 O(nlogn)和 O(1)
|
36
azhangbing 2018-12-03 17:29:44 +08:00 via iPhone 1
不错不错
|
37
july1995 2018-12-03 18:07:10 +08:00 1
优秀,考研党正在复习数据结构的查找与排序。
|
38
rayjoy 2018-12-03 20:20:36 +08:00
做的很用心了,收藏一下。
|
39
CoderOnePolo OP @hei1000 文章都在微信公众号里面,以前发了几篇文章在这里,但感觉有点不好,就没全发。
|
40
CoderOnePolo OP |