11排序（上）：为什么插入排序比冒泡排序更受欢迎？.pdf

11|排序（上）：为什么插入排序比冒泡排序更受欢迎？ 11|排序（上）：为什么插入排序比冒泡排序更受欢迎？ 排序对于任何一个程序员来说，可能都不会陌生。你学的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常 会用到排序。排序非常重要，所以我会花多一点时间来详细讲一讲经典的排序算法。 排序算法太多了，有很多可能你连名字都没听说过，比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮，也是最经典的、最常用的：冒泡 排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。我按照时间复杂度把它们分成了三类，分三节课来讲解。 file:///F/temp/geektime/数据结构与算法之美/11排序（上）：为什么插入排序比冒泡排序更受欢迎？.html[2019/1/15 15:35:26] 11|排序（上）：为什么插入排序比冒泡排序更受欢迎？ 2 带着问题去学习，是最有效的学习方法。所以按照惯例，我还是先给你出一个思考题：插入排序和冒泡排序的时间复杂度相同，都是O(n ) ，在实际的软件开发 里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？ 你可以先思考一两分钟，带着这个问题，我们开始今天的内容！ file:///F/temp/geektime/数据结构与算法之美/11排序（上）：为什么插入排序比冒泡排序更受欢迎？.html[2019/1/15 15:35:26] 11|排序（上）：为什么插入排序比冒泡排序更受欢迎？ “ ” 如何分析一个 排序算法 ？ 学习排序算法，我们除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法，要从哪几个方面入手呢？ 排序算法的执行效率 对于排序算法执行效率的分析，我们一般会从这几个方面来衡量： 1.最好情况、最坏情况、平均情况时间复杂度 我们在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序 的原始数据是什么样的。 为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完 全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。 2.时间复杂度的系数、常数、低阶 n 我们知道，时间复杂度反应的是数据规模 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能 10 100 1000 是 个、 个、 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。 3.比较次数和交换（或移动）次数 这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如 果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。 排序算法的内存消耗 我们前面讲过，算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排 序 （Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。我们今天讲的三种排序算法，都是原地排序算法。 排序算法的稳定性 仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在 值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 2 9 3 4 8 3