算法-排序(上)

发表于 | 更新于 | 分类于 | 阅读次数：

前言


排序对一个程序员来说，可能都不会陌生。大部分编程语言中，也都提供了排序函数。在平常的项目中，也经常会用到排序。排序非常重要，所以会分几节详细讲一讲经典的排序算法。

排序算法太多了，可能有的连名字都没有听说过，比如猴子排序、睡眠排序、面条排序等等。这里只列举众多排序算法众多的一小撮，也是最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度把他们分成了三类，分上中下三节来讲。

排序算法 时间复杂度 是否基于比较
上 冒泡、插入、选择 $ O(n^2) $ √
中 快排、归并 $ O(nlogN) $ √
下 桶、计数、基数 $ O(n) $ ×

带着问题去学习，是最有效的学习方法。所以按照惯例，先给出思考题：插入排序和冒泡排序的时间复杂度相同，都是$O(n^2)$，在实际软件开发里，为什么更倾向于使用插入排序而不是冒泡排序呢？


如何分析一个排序算法


学习排序算法，除了学习他的算法原理、代码实现之外，更重要的是学会如何评价、分析一个排序算法。那么要分析一个排序算法，要从哪几方面入手呢？

一、 算法的执行效率

对于排序算法的执行效率的分析，我们一般会从以下几点来进行衡量：

1、最好情况、最坏情况、平均情况时间复杂度

我们在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好情况、最坏情况时间复杂度对应的要排序的原始数据是什么样。

为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的接近无序。有序度不同的数据集，对于排序的执行时间肯定会有影响的，我们要知道排序算法在不同数据下的性能表现。

2、时间复杂度的系数、常数、低阶

我们知道，时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是10个、100个、1000个这样数据规模较小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3、比较次数和交换次数

这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程中，会涉及两种操作，一个是元素比较大小，另一个是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换次数考虑进去。

二、 算法的内存消耗

前面讲过算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过针排序算法的空间复杂度，我们引入一个新概念，原地排序。原地排序算法，就是特指空间复杂度为O(1)的排序算法，我们这节讲的三种排序算法都是原地排序算法。

三、 排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相同的元素，经过排序之后，相等元素之间原有的先后顺序不变。

我通过一个例子来解释一下。比如我们有一组数据2,9,3,4,8,3，按照大小排序之后就是2,3,3,4,8,9。

这组数据里有两个3，经过某种排序算法排序之后，如果两个3的前后顺序没有改变，那我们就把这种排序算法叫做稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫做不稳定的排序算法。

你可能要问了，这两个3哪个在前，哪个在后有什么关系啊。稳不稳定又有什么关系呢？为什么要考察排序算法的稳定性呢？

很多数据结构和算法的课程，再讲排序的时候，都是用整数来举列的。但在真正的软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。

比如说，我们现在要给电商交易系统的“订单”排序，订单有两个属性，一个是下单时间，一个是订单金额。如果我们现在有10万条订单数据，我们希望按照订单金额从小到大对订单数据进行排序，对于金额相同的订单，我们希望按照下单时间从早到晚有序，对于这样一个排序需求，我们怎么来做呢？

最先想到的方法是，我们先按照金额对订单数据进行排序，然后，在遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单的时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。

但是借助稳定排序算法，这个问题可以非常简洁的解决。解决思路是这样的，我们先按照下单时间给订单排序，注意是下单时间，不是订单金额，排序完成之后，我们再用稳定排序算法，按照订单金额重新排序。这样两遍排序之后，我们得到的就是订单数据按照金额大小从小到大排序，金额相同的订单按照下单时间从早到晚排序的。为什么呢？

稳定排序算法可以保持金额相同的两个对象，再排序前后的顺序保持不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。


冒泡排序


我们从冒泡排序开始，学习今天的三种排序算法。

冒泡排序只会操作相邻的两个数据。每次冒泡排序都会对相邻的两个数据进行比较，看是否满足大小关系要求，如果不满足就让它两互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了对n个数据的排序工作。

我用一个例子，带你看下冒泡排序的整个过程。我们要对一组数据4,5,6,3,2,1，从小到大进行排序。第一次冒泡排序的详细过程就是这样：

可以看出，经过第一次冒泡排序之后，6这个元素已经存储在正确的位置上了。要想完成所有数据的排序，我们只需要进行6次这样的冒泡排序操作就对了。

实际上，刚才的冒泡排序还可以优化，当某次操作已经没有数据交换时，说明已经完全有序，不需要在执行后续的冒泡操作了。我这里给一个例子，这里面给6个元素排序，只需要4次冒泡操作就可以了。

冒泡次数 冒泡结果 是否有数据交换
初始状态 3，5，4，1，2，6 -
第一次冒泡 3，4，1，2，5，6 有
第二次冒泡 3，1，2，4，5，6 有
第三次冒泡 1，2，3，4，5，6 有
第四次冒泡 1，2，3，4，5，6 无，结束排序操作

冒泡排序算法的原理比较好理解，具体的代码如下，你可以结合代码理解原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 冒泡排序 a表示需要排序的数组 n表示数组的大小
public void bubbleSort(int[] a,int n){
    for(int i=0;i<n-1;i++){
        boolean flag = false;
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = true;
            }
        }
        if(!flag) break;
    }
}

现在结合上面分析算法的三个方面，有三个问题要问你。

第一、冒泡排序是原地排序算法吗？

冒泡的过程只涉及相邻两个数据的交换操作，字需要一个常量级的临时空间，所以它的空间复杂度是O(1)，是一个原地排序算法。

第二、冒泡排序是稳定的排序算法吗？

在冒泡排序中，只有交换才可以改变两个元素的前后位置。为了保证冒泡排序算法的稳定性，当有相邻的两个元素相等时，我们不做交换，相同大小的数据在排序前后不改变顺序，所以冒泡排序算法是稳定的排序算法。

第三、冒泡排序的时间复杂度是多少？

最好的情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡排序就可以了，所以最好的时间复杂度为$O(n)$。而在最坏情况下，要排序的数据是倒序排列的，我们需要进行n次冒泡排序，所以最坏情况时间复杂度为$O(n^2)$。

最好、最好情况时间复杂度很容易区分，那平均情况时间复杂度是多少呢？我们前面讲过，平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。

对于包含n个元素的数组，这n个数据有 n! 种排列方式。不同的排列方式，冒泡排序执行的时间是不同的。比如我们前面举的那个例子，一个需要6次冒泡，而另一个只需要4次。如果用概率论的方法定量分析平均时间复杂度，那涉及到的数学推理和计算就会很复杂。我这里还有一种思路，通过有序度和逆序度这两个概念来分析。

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样： $a[i] <= a[j], 如果i < j$。

2,4,3,1,5,6 这组数据的有序度为11。因其有序元素对为11个，分别是: (2,4) (2,3) (2,5) (2,6) (4,5) (4,6) (3,5) (3,6) (1,5) (1,6) (5,6)

同理，对于一个倒序排列的数组，比如 6,5,4,3,2,1，有序度为0；对于一个完全有序的数组，比如1,2,3,4,5,6，有序度就是n*(n-1)/2，也就是15.我们把完全有序的数组的有序度叫做满有序度。

逆序度的定义正好跟有序度的定义相反(默认从小到大为有序)，我想你已经想到了。关于逆序度，我们就不举例子说明了。你可以结合有序度的例子自己看一下：$a[i] > a[j], 如果i < j$。

关于这三个概念，我们可以得到一个公式：逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

我还是拿前面举得那个冒泡排序的例子说明。要排序的数组的初始状态为4,5,6,3,2,1，其中，有序元素对(4,5)、(4,6)、(5,6)，所以有序度为3。 n=6，所以排序完成之后终态的满有序度为15.

冒泡次数 冒泡结果 有序度
初始状态 4，5，6，3，2，1 3
第一次冒泡 4，5，3，2，1，6 6
第二次冒泡 4，3，2，1，5，6 9
第三次冒泡 3，2，1，4，5，6 12
第四次冒泡 2，1，3，4，5，6 14
第五次冒泡 1，2，3，4，5，6 15

冒泡排序包含两个原子操作，比较和交换。每交换一次，有序度就加1,。不管算法怎么改进，交换次数是确定的，即为逆序度，也就是n*(n-1)/2 - 初始有序度。此例中就是15-3=12，也就是要进行12次交换操作。

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度为0，所有要进行n*(n-1)、2次交换。最好情况下，初始状态的有序度为满有序度，就不需要进行交换。我们去平均值n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。

换句话说，平均情况下需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而时间复杂度的上限位$O(n^2)$，所以平均情况下的时间复杂度就是$O(n^2)$。

这个平均时间复杂度的推导过程并不严格，但是很多时候很有用，毕竟概率论的定量分析太复杂，不太好用。


插入排序


我们先来看一个问题。如果一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。

这是一个动态排序的过程，即动态的往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，我们也可以借鉴上面讲的插入方法，来进行排序，于是就有了插入排序算法。

那插入排序是如何借助上面的思想来实现排序的呢？

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组中的第一个元素。插入排序算法的核心思想是取未排序区间的元素，在已排序区间中找到合适的位置插入，并保证已排序区间中的元素一直有序，重复这个过程，知道未排序区间中元素为空，算法结束。

如图所示，要排序的数据是4,5,6,1,3,2，其中左侧为已排序区间，右侧为未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个元素a插入到已排序区间时，需要先拿a和已排序区间的元素一次比较大小，找到合适的位置插入。找到插入点之后，我们还需要将插入点之后的额元素顺序往后移动一位，这样才能腾出空间为元素a插入。

对于不同的查找插入点的方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数是固定的，就等于逆序度。

为什么说移动次数就等于逆序度呢？我拿刚才的例子画一个图表，你一看就明白了。满有序度是n*(n-1)/2=15, 初始有序度为5，所以逆序度为10,。插入排序中，数据移动的个数总和也等于3+3+4=10。

插入排序的原理也很简单吧。你也可以结合一下代码理解插入排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void insertSort(int[] a, int n){
	if(n<=1) return;
	for(int i=1;i<n;i++){
		int val = a[i];
		int j=i-1;
		for(;j>0;j--){
			if(a[j]>val){
				a[j+1] = a[j];
			}else {
				break;
			}
		}
		a[j+1] = val;
	}
}

现在同样有三个问题。

第一、插入排序是原地排序算法吗？

从实现过程可以明显的看出，插入排序的运行不需要额外的存储空间，所以插入排序的空间复杂度为O(1)，是一个原地排序算法。

第二、插入排序是稳定的排序算法吗？

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现的元素的后面，这样就可以保持原有的前后顺序不变，所有插入排序是稳定排序算法。

第三、插入排序的时间复杂度是多少？

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数组里查找插入位置，每次只需比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要搬移大量的数据，所以最坏情况下的时间复杂度为$O(n^2)$。

还记得我们在一个数组中插入一个数据的平均复杂度是多少吗？没错，是O(n)，所以对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，执行n次插入操作，所以平均时间复杂度为$O(n^2)$。


选择排序


选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小元素，将其放到已排序区间的末尾。

同样，也有三个问题需要你思考。

第一、插入排序是原地排序算法吗？

首先选择排序的空间复杂度为O(1)，所以是一种原地排序算法。

第二、插入排序的时间复杂度是多少？

选择排序最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度均为$O(n^2)$。你可以自己分析看看。

第三、插入排序是稳定的排序算法吗？

答案是否定的，选择排序是一种不稳定的排序算法。从选择排序的原理示意图可以看出，选择排序每次都要找剩余排序元素中的最小值，并和前面元素交换位置，这就破坏了稳定性。

比如5,8,5,2,9这样一组数据，使用选择排序来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5个中间5的顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

1
2
3
4
5
6
7
8
9
10
11
public void selectSort(int[] a, int n){
    for(int i=0;i<n-1;i++){
        for(int j=i+1; j<n-1;j++){
        	if(a[j]<a[i]){
        		int temp = a[j];
        		a[j] = a[i];
        		a[i] = temp;
        	}
        }
    }
}

解答开篇


基本的知识都讲完了，我们来看看开篇的问题：冒泡排序和插入排序的时间复杂度都为$O(n^2)$，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？

我们前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定的值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，移动次数等于原始数据的逆序度。

但是从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要一个。我们来看一下下面这段操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 冒泡排序中的数据交换操作
 if(a[j]>a[j+1]){
    int temp = a[j];
    a[j] = a[j+1];
    a[j+1] = temp;
    flag = true;
}

// 插入排序中数据移动操作
if(a[j]<val){
    a[j+1] = a[j];
}else {
    break;
}

我们把执行一个赋值语句的时间粗略的估计为单位时间unit_time，然后分别用冒泡排序和插入排序对同一个逆序度为K的数组进行排序。用冒泡排序需要K次交换操作，每次需要3个赋值语句，所以交换操作总耗时就是3K单位时间。而插入排序中数据移动操作只需要K个单位时间。

所以，虽然冒泡排序和插入排序的时间复杂度是一样的，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间，我们只讲了最基础的一种。如果你对插入排序的优化感兴趣，可以自己学习一下希尔排序。


内容小结


想要分析、评价一个排序算法，需要从执行效率、内存消耗和稳定性三个方面来看。因此这一节，分析了三种时间复杂度为$O(n^2)$的排序算法：冒泡排序、插入排序、选择排序。需要重点掌握的是它们的分析方法。

排序算法 是否原地排序 是否稳定 最好 最坏 平均
冒泡排序 √ √ $O(n)$ $O(n^2)$ $O(n^2)$
插入排序 √ √ $O(n)$ $O(n^2)$ $O(n^2)$
选择排序 √ × $O(n^2)$ $O(n^2)$ $O(n^2)$

这三种时间复杂度为$O(n^2)$的排序算法中，冒泡排序、选择排序可能就纯粹停留在理论的层面了，实际开发中应用并不多，但是插入排序还是挺有用的。后面讲排序优化的时候，有些语言的排序函数的实现会用到插入排序算法。

今天讲的三种算法，实现代码都非常简单，对于小规模的数据排序，用起来非常高效，但是在大规模数据排序的时候，这个时间复杂度就稍微有点高了。所以我们更倾向于使用下一节讲的时间复杂度为$O(n*logn)$的排序算法。

课后思考

我们讲过，特定的算法是依赖于特定的数据结构的。我们今天讲的几种排序算法，都是基于数组实现的。如果数组存储在链表中，这三种排序算法还能工作吗？如果能，相应的时间、空间复杂度又是多少？