+
+

数据结构与算法之美:排序

排序算法有很多,有很多我们可能连名字都没听过,比如猴子排序、睡眠排序、面条排序等。但是最经典的、最常用的排序,还是冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

排序算法的评价标准

学习排序算法,我们除了学习它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。

我们已经学过了「时间复杂度」和「空间复杂度」,那么这两个复杂度可以分别作为执行效率和内存消耗的评价标准,除此之外,还有一个重要的度量指标,「稳定性」。

执行效率

  1. 最好、最坏复杂度,平均时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数和交换次数

在计算平均复杂度时,我们通常要用概率论的方法来计算加权平均期望,涉及的数学推理和理论计算就会比较复杂。这里我们还可以利用「有序度」和「逆序度」两个概念来分析。

有序度指的是数组中具有时序关系的元素对的个数,比如:

对于一个完全倒序排列的数组,有序度是0;对于一个完全正序的数组,有序度是$\frac{n\times (n-1)}{2}$,称为「满有序度」。

而逆序度恰好相反,如果说有序度是从小到大,那么逆序度就是从大到小。

关于有序度、逆序度、满有序度,有这么一个公式:

1
逆序度 = 满有序度 - 有序度

了解了这些概念后,我们可以将排序的过程看作是增加有序度、减少逆序度,直到达到满有序度的过程。

而排序中,每交换一次,有序度就加1。不管算法怎么改进,总共的交换次数是确定的,即为逆序度。我们知道,最好情况下,初始有序度为满有序度,不需要进行交换;最坏情况下,初始有序度为0,那么就要进行$\frac{n\times(n-1)}{2}$次交换操作。那么平均下来就要进行$\frac{n\times(n-1)}{4}$次交换操作。

借助有序度和逆序度,我们可以得到平均交换次数,进而根据不同算法得到平均比较次数,最终求得平均时间复杂度。

内存消耗

针对排序算法的空间复杂度,我们还引入了一个新的概念,原地排序(Sorted in place)。原地排序算法,就是指空间复杂度是 O(1) 的排序算法。

稳定性

稳定性是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

举个例子,比如我们有一组数据2,9,3,4,8,3,按照大小排序之后就是2,3,3,4,8,9。这组数据里有两个3。经过某种排序算法排序之后,如果两个3的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。

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

在真正软件开发中,我们要排序的往往不是单纯的整数,而是一组对象,我们需要按照对象的某个 键值来排序。比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有10万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。

那么,我们的思路一般是先按照金额进行排序,然后对相同金额的订单再按照下单时间排序。稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。第一次排序之后,所有的订单按照下单时间从早到晚有序了。在第二次排序中,如果使用的是稳定的排序算法,那么即便经过第二次排序,相同金额的订单仍然保持下单时间从早到晚有序。

冒泡排序

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

举个例子,对一组4 5 6 3 2 1进行排序,第一次冒泡操作的详细过程如图:

而要完成所有数据的排序,需要进行6次冒泡操作:

实际上,冒泡排序还可以进行优化——当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。比如3 5 4 1 2 6这个例子:

要实现冒泡排序的代码很简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var bubbleSort = function (arr) {
for (var i = 0; i < arr.length; i++) { //最多要进行多少次冒泡操作
var flag = false;
for (var j = 0; j < arr.length - i - 1; j++) { //每次冒泡排序从开头到未排序部分的终点
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag) break;
}
return arr
};

评估

  1. 冒泡排序的时间复杂度?
    最好:$O(n)$
    最坏:$O(n^2)$
    平均:上面说过,排序算法的平均交换次数为$\frac{n\times(n-1)}{2}$,而比较操作肯定比交换操作多,那么可以表示为$\frac{n\times(n-1)}{2}+m$,复杂度的上限是$O(n^2)$,那么简化的平均时间复杂度也就为$O(n^2)$。

  2. 冒泡排序是原地排序算法吗?
    冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间temp,所以它的空间复杂度为$O(1)$,属于原地排序算法。

  3. 冒泡排序是稳定的排序算法吗?
    在冒泡排序中,当相邻元素相等时,是不做交换的,所以冒泡排序是稳定的排序算法。

插入排序

插入排序的思想是在已排序区间中插入未排序的元素。初始已排序区间只有一个元素,即为数组的第一个元素。重复插入过程,直到不存在未排序的元素。

插入排序包含两种操作:

  1. 元素的比较
    当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。
  2. 元素的移动
    找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

用JavaScript实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
var insertionSort = function (arr) {
for (var i = 1; i < arr.length; i++) {
var cur = i;
var curValue = arr[cur];
while (curValue < arr[cur - 1]) {
arr[cur] = arr[cur - 1]; // 数据后移
cur--;
}
arr[cur] = curValue; // 插入数据
}
return arr;
};

评估

  1. 插入排序的时间复杂度?
    最好:$O(n)$
    最坏:$O(n^2)$
    平均:在数组中插入一个数据的平均时间复杂度是$O(n)$,而插入排序每次循环都相当于在数组中插入一个新的数据,一共循环n次,所以平均时间复杂度为$O(n^2)$。

  2. 插入排序是原地排序算法吗?
    插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是$O(1)$,也就是说,这是一个原地排序算法。

  3. 插入排序是稳定的排序算法吗?
    在插入排序中,当相邻元素相等时,同样是不做搬移和插入的,所以插入排序是稳定的排序算法。

为什么插入排序比冒泡排序更受欢迎

理论上来说,无论如何优化,冒泡排序和插入排序对元素的交换/移动次数都是原始数据的逆序度。但是,从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。

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

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

选择排序

选择排序每次循环从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

选择排序的思想很容易理解,就不赘述了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var selectionSort = function (arr) {
for (var i = 0; i < arr.length; i++) {
var minValue = arr[i];
var minIndex = i;
for (var j = i; j < arr.length; j++) {
if (arr[j] < minValue) {
minValue = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = minValue;
}

return arr
};

评估

  1. 选择排序的时间复杂度?
    最好:$O(n^2)$
    最坏:$O(n^2)$
    平均:$O(n^2)$

  2. 选择排序是原地排序算法吗?
    选择排序算法的运行并不需要额外的存储空间,所以空间复杂度是$O(1)$,是一个原地排序算法。

  3. 选择排序是稳定的排序算法吗?
    选择排序是一种不稳定的排序算法。从前面那张图中,可以看出来,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

归并排序

归并排序的核心思想是分治——如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

用JavaScript这样实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var mergeSort = function (arr) {
if (arr.length <= 1) return arr;

var mergeArr = function (arr1, arr2) {
var temp = [];
while (arr1.length || arr2.length) {
if (arr1.length === 0) temp.push(arr2.shift());
else if (arr2.length === 0) temp.push(arr1.shift());
else if (arr1[0] <= arr2[0]) {
temp.push(arr1.shift());
} else temp.push(arr2.shift());
}
return temp;
};

var mid = parseInt((arr.length) / 2);
return mergeArr(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid, arr.length)));
};

评估

  1. 归并排序的时间复杂度?
    假设对n个元素进行归并排序需要的时间是$T(n)$,那分解成两个子数组排序的时间都是$T(\frac{n}{2})$。而merge进行合并操作的时间复杂度为$O(n)$。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是$T(n)=2\times T(\frac{n}{2})+n$。对此公式进行递推,可以得到$T(n)=2^k\times T(\frac{n}{2^k})+k\times n$,当$T(\frac{n}{2^k})=T(1)$时,得到$k=\log _2n$,再代回,就得到$T(n)=Cn+n\log _2n$。

所以归并排序的时间复杂度是$O(n\log n)$。可以看出,归并排序的执行效率与要排序的原始数组的有序程度无关,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是$O(n\log n)$。

  1. 归并排序是原地排序算法吗?
    尽管每次归并操作都需要申请额外的内存空间temp,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小,所以空间复杂度是$O(n)$。

  2. 归并排序是稳定的排序算法吗?
    如果arr1arr2之间有值相同的元素,那只要先把确保先把arr1中的元素放入temp数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定的排序算法。

快速排序

快排的思想是这样的:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

根据分治、递归的处理思想,我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据,直到区间缩小为1,就说明所有的数据都有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var quickSort = function (arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
var i = left;
var j = right;

const pivot = arr[right];

while (i < j) {
while (i < j && arr[i] <= pivot) {
i++; // 找到左边比pivot大的第一个元素(从左往右)
}![](https://pic.rhinoc.top/mweb/15699297975497.jpg)

arr[j] = arr[i]; // 放到pivot原本的位置

while (i < j && arr[j] >= pivot) {
j--; // 找到右边比pivot小的第一个元素(从右往左)
}
arr[i] = arr[j]; // 放到左边之前找到的较大元素的位置
}

arr[j] = pivot; // 原本的pivot的值赋给刚刚找到较小元素的位置

quickSort(arr, left, j - 1); //对左边排序
quickSort(arr, j + 1, right); //对右边排序

return arr;
};

快排和归并的区别

归并排序的处理过程是由下到上的,先处理子问题,然后再合并。而快排正好相反,它的处理过程是由上到下的,先分区,然后再处理子问题。归并排序虽然是稳定的、时间复杂度为$O(n\log n)$的排序算法,但是它是非原地排序算法。我们前面讲过,归并之所以是非原地排序算法,主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数,可以实现原地排序,解决了归并排序占用太多内存的问题。

评估

  1. 快速排序的时间复杂度?
    如果每次分区操作,都能正好把数组分成大小接近相等的两个小区间,那快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是$O(n\log n)$。

所以归并排序的时间复杂度是$O(n\log n)$。可以看出,归并排序的执行效率与要排序的原始数组的有序程度无关,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是$O(n\log n)$。

  1. 快速排序是原地排序算法吗?
    是。

  2. 快速排序是稳定的排序算法吗?
    是。

为什么快速排序比归并排序应用更广泛?

归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,过程非常相似。理解归并排序的重点是理解递推公式和合并函数。同理,理解快排的重点也是理解递推公式,还有分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是$O(n)$。正因为此,它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是$O(n^2)$,但是平均情况下时间复杂度都是 $O(n\log n)$。不仅如此,快速排序算法时间复杂度退化到$O(n^2)$的概率非常小,我们可以通过合理地选择pivot来避免这种情况。

总结

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

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_8/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay
0%