这是一个创建于 2188 天前的主题，其中的信息可能已经有所发展或是发生改变。
在前面的章节中详细的讲解分析了十大经典排序算法，本文将进行一个大总结同时分析它们的时间复杂度与稳定性。
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括：
关于时间复杂度：
- 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
- 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
- O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
- 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
-
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
-
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 归并排序
6. 快速排序
7. 堆排序
8. 计数排序
9. 桶排序
10. 基数排序
Tip 为了演示更加清楚，本文中所有的动画都放慢了速度，因此 GIF 大小对比之前会有所增大，图片加载速度会变慢，如果你想获取所有的超清动画，在公众号 五分钟学算法 回复 v2ex 可获得资料。
第 1 条附言 · 2018-12-03 09:36:27 +08:00
修正堆排序：
第 2 条附言 · 2018-12-03 12:31:46 +08:00
没想到能有这么多收藏，感谢各位大佬支持，感兴趣的话可以关注一波公众号^_^
 |
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 |
Select Language