十大排序算法(优化篇)

一. 引言

Hello, 小伙伴们, 算法系列又更新了, 在上篇(入门篇)文章中介绍了两种排序算法, 分别是冒泡排序和插入排序，但是这两种排序算法的时间复杂度都是平方阶的，那在这篇文章中会对冒泡排序进行优化，并且会引入第三种排序算法—— 快速排序。

声明：算法核心思想都是一样的, 不分编程语言, 但是在本系列文章中主要会用 python 或者 JavaScript 语言来实现相关代码, 特此说明一下。

想查看更多的文章请关注公众号：IT巡游屋

二. 冒泡排序的优化

在上篇文章中我们分析了冒泡排序算法，不管是什么情况，冒泡排序算法的时间复杂度始终是平方阶，但是比方说一个数组本身就是排好序的数组，或者在执行一些步骤时就已经排好序了，那么理想的状态就应该停止执行。

2.1 回顾

下面先复习下之前的冒泡排序算法:

现在对序列 A 进行冒泡排序, 步骤如下: 1. 对比第 1 个元素(记为 A[1]) 和 第 2 个元素(记为 A[2]), 如果A[1] > A[2], 就交换这两个元素; 2. 再次对比 A[2] 和 A[3], 如果 A[2] > A[3], 就交换这两个元素; 3. 重复上述步骤, 直到对比 A[n-1] 和 A[n], 如果 A[n-1] > A[n], 就交换这两个元素, 此时 A[n] 一定是最大的那个元素; 4. 再次对 A[1...n-1] 循环执行第 1~3 的步骤, 直到 对比 A[n-2] 和 A[n-1], 如果 A[n-2] > A[n-1], 就交换这两个元素; 5. 重复执行步骤 4, 直到排序完成.

2.2 优化一

2.2.1 算法描述

核心思想: 在原来的基础上设置一个 标记变量, 初始值为 true, 如果在一次循环中并没有进行任何交换, 就停止排序算法.

2.2.2 算法伪代码

// BubbleSort(A), 参数 A 表示排序的数组或者列表 for j = 1 to A.length - 1 swapped = false for i = 1 to A.length - j if A[i] > A[i+1] A[i], A[i + 1] = A[i + 1], A[i] swapped = true // 如果没有发生转换, 则跳出循环 if !swapped break

2.2.3 算法演绎

为了便于对上述算法更简单的理解, 我们用一个具体的序列 $A=[8,3,1,5,4]$ 演绎一下冒泡排序的执行步骤.

第 1 次循环 —— $j=1$, $i$ 循环 4 次

A = [8, 3, 1, 5, 4] 1. 首先比较 A[1]=8 与 A[2]=3, 此时 8 > 3, 将 A[1] 和 A[2] 交换位置, 此时 A = [3, 8, 1, 5, 4]; 2. 然后比较 A[2]=8 与 A[3]=1, 此时 8 > 1, 将 A[2] 和 A[3] 交换位置, 此时 A = [3, 1, 8, 5, 4]; 3. 然后比较 A[3]=8 与 A[4]=5, 此时 8 > 5, 将 A[3] 和 A[4] 交换位置, 此时 A = [3, 1, 5, 8, 4]; 4. 然后比较 A[4]=8 与 A[5]=4, 此时 8 > 4, 将 A[4] 和 A[5] 交换位置, 此时 A = [3, 1, 5, 4, 8]; 此时可以看到 A[5] = 8 就是最大值;

图形演示如下:

第 2 次循环 —— $j=2$, $i$ 循环 3 次

此时 A = [3, 1, 5, 4, 8] 1. 首先比较 A[1]=3 与 A[2]=1, 此时 3 > 1, 将 A[1] 和 A[2] 交换位置, 此时 A = [1, 3, 5, 4, 8]; 2. 然后比较 A[2]=3 与 A[3]=5, 此时 3 < 5, 进入下一轮循环; 3. 然后比较 A[3]=5 与 A[4]=4, 此时 5 > 4, 将 A[3] 和 A[4] 交换位置, 此时 A = [1, 3, 4, 5, 8];

图形演示如下:

第 3 次循环 —— $j=3$, $i$ 循环 2 次

此时 A = [1, 3, 4, 5, 8] 1. 首先比较 A[1]=1 与 A[2]=3, 此时 1 < 3, 进入下一轮循环; 2. 然后比较 A[2]=3 与 A[3]=4, 此时 3 < 4, 不发生交换; 3. 可知在此轮循环中未发生交换, 此时退出冒泡排序.

可知, 如果用原来的冒泡排序算法, 需要经历 4 个步骤(循环), 但是 经过优化之后只需 3 个步骤 就完成排序了.

2.2.4 算法实现

// 在 js 中, 数组的编号是从 0 开始计数的, A[0] 表示的是数组 A 的第一个数字 function BubbleSort(A) { for (var j = 0; j < A.length - 1; j++) { // 在每一轮开始将 swapped 设置为 false var swapped = false; for (var i = 0; i < A.length - 1 - j; i++) { if (A[i] > A[i + 1]) { var temp = A[i]; A[i] = A[i + 1]; A[i + 1] = temp; // 如果此循环发生了交换, 就将 swapped 设置为 true swapped = true; } } // 如果此轮没有发生交换, 则退出外层循环, 也就是退出排序算法 if (!swapped) break; } return A } // 算法测试, 通过调试可以清楚的看到上面的算法演绎的过程 A = [8, 3, 1, 5, 4] console.log(BubbleSort(A));

2.2.5 算法分析 —— 时间复杂度

为了便于计算时间复杂度, 对于单行代码执行的时间复杂度记为 1。最坏的情况此时就不分析了, 因为和上一次是一致的, 也就是平方阶 $O(n^2)$ 。

但是最好的情况， 比如本身就是已经排好序的数组， 那么只需执行一轮循环就可以了，此时冒泡排序的时间复杂度就是线性阶 $O(n)$ 了，可见此时时间复杂度就明显降低了。

2.3 优化二

2.3.1 算法描述

核心思想: 此优化方法是在优化一的基础上的进一步优化, 主要是为了减少二层循环的次数, 记录上一轮未经过排序的元素的最大下标, 那么下一次循环的最大次数只需到达这个位置就可以, 无需再往后进行循环了.

2.2.2 算法伪代码

// BubbleSort(A), 参数 A 表示排序的数组或者列表 for j = 1 to A.length - 1 swapped = false // 未经过排序的元素的最大下标 indexOfLastUnsortedElement = A.length - 1 // 上次发生交换的位置 int swappedIndex = -1 for i = 1 to indexOfLastUnsortedElement if A[i] > A[i+1] A[i], A[i + 1] = A[i + 1], A[i] swapped = true // 更新交换的位置 swappedIndex = i // 未经过排序的元素的最大下标就是最后一次发生交换的位置 indexOfLastUnsortedElement = swappedIndex; // 如果没有发生转换, 则跳出循环 if !swapped break

2.2.3 算法演绎

为了便于对上述算法更简单的理解, 我们用一个具体的序列 $A=[8,3,1,4,5]$ 演绎一下冒泡排序(优化二)的执行步骤.

第 1 次循环 —— $j=1$, $i$ 循环 4 次

A = [8, 3, 1, 4, 5] 1. 首先比较 A[1]=8 与 A[2]=3, 此时 8 > 3, 将 A[1] 和 A[2] 交换位置, 此时 A = [3, 8, 1, 4, 5]; 2. 然后比较 A[2]=8 与 A[3]=1, 此时 8 > 1, 将 A[2] 和 A[3] 交换位置, 此时 A = [3, 1, 8, 4, 5]; 3. 然后比较 A[3]=8 与 A[4]=4, 此时 8 > 4, 将 A[3] 和 A[4] 交换位置, 此时 A = [3, 1, 4, 8, 5]; 4. 然后比较 A[4]=8 与 A[5]=5, 此时 8 > 5, 将 A[4] 和 A[5] 交换位置, 此时 A = [3, 1, 4, 5, 8]; 此时可以看到 A[5] = 8 就是最大值, 同时未经过排序的元素的最大下标就是 4, 指的是 A[4] = 5 这个元素;

图形演示如下:

第 2 次循环 —— $j=2$, $i$ 循环 3 次

此时 A = [3, 1, 4, 5, 8] 1. 首先比较 A[1]=3 与 A[2]=1, 此时 3 > 1, 将 A[1] 和 A[2] 交换位置, 此时 A = [1, 3, 4, 5, 8]; 2. 然后比较 A[2]=3 与 A[3]=4, 此时 3 < 4, 进入下一轮循环; 3. 然后比较 A[3]=4 与 A[4]=5, 此时 4 < 5, 进入下一轮循环; 未经过排序的元素的最大下标是 1, 指的是 A[1] = 1 这个元素.

图形演示如下:

第 3 次循环 —— $j=3$, $i$ 循环 0 次

此时 A = [1, 3, 4, 5, 8] 此时第二层循环直接退出, 不再进行, 也就是没有发生交换, 退出冒泡排序.

可知, 如果用原来的冒泡排序算法, 需要经历 4 个步骤(循环), 但是 经过优化之后也只需 3 个步骤 就完成排序了.

2.2.4 算法实现

// 在 js 中, 数组的编号是从 0 开始计数的, A[0] 表示的是数组 A 的第一个数字 function BubbleSort(A) { for (var j = 0; j < A.length - 1; j++) { // 在每一轮开始将 swapped 设置为 false var swapped = false; // 未经过排序的元素的最大下标 var indexOfLastUnsortedElement = A.length - 1; // 上次发生交换的位置 var swappedIndex = -1; for (var i = 0; i < indexOfLastUnsortedElement; i++) { if (A[i] > A[i + 1]) { var temp = A[i]; A[i] = A[i + 1]; A[i + 1] = temp; // 更新交换的位置 swappedIndex = i; // 如果此循环发生了交换, 就将 swapped 设置为 true swapped = true; } } // 未经过排序的元素的最大下标就是最后一次发生交换的位置 indexOfLastUnsortedElement = swappedIndex; // 如果此轮没有发生交换, 则退出外层循环, 也就是退出排序算法 if (!swapped) break; } return A } // 算法测试, 通过调试可以清楚的看到上面的算法演绎的过程 A = [8, 3, 1, 4, 5] console.log(BubbleSort(A));

2.2.5 算法分析 —— 时间复杂度

为了便于计算时间复杂度, 对于单行代码执行的时间复杂度记为 1。最坏的情况此时就不分析了, 因为和上一次是一致的, 也就是平方阶 $O(n^2)$ 。

但是最好的情况， 就是本身就是已经排好序的数组， 那么也是只需执行一轮循环就可以了，此时冒泡排序的时间复杂度就是线性阶 $O(n)$ 了，可见此时时间复杂度就明显降低了，对于某些情况，此优化方式比优化一的执行次数更少， 算法更优。

三. 快速排序 (QuickSort)

从以上分析我们可以发现, 不管如何优化冒泡排序算法, 它的时间复杂度始终都是平方阶的, 插入排序也同样, 那有没有一种排序算法的时间复杂度不是平方阶的呢? 答案是有的, 那就是将要介绍的 快速排序 算法。

声明: 之前在介绍算法时, 数组的第一个元素都是从 1 开始的, 考虑到大部分读者都是有一定的编程基础的, 那从这里开始, 数组的第一个元素就从 0 开始.

3.1 算法描述

现在对序列 A 进行快速排序, 假设 end = A.length -1, 步骤如下:

首先取出数组中的任意一个元素比如 A[0] = pivotKey(主元), 然后将 元素pivotKey 与数组中的所有元素依次对比, 如果元素比 pivotKey 小, 就交换这两个元素的位置, 最终可以保证 元素pivotKey 的左侧都是比它小的元素, 右侧都是比它大的元素, 假设此时 元素pivotKey 的位置是 pivot;

然后再对 A[0, pivot - 1] 和 A[pivot + 1, end] 执行 1 的步骤.

从上面可以看出最关键的就是步骤 1 , 它将数组分为了 三个部分, 分别是 A[0, pivot - 1], A[pivot], A[pivot + 1, end].

3.2 算法伪代码

// QuickSort(A, start, end) 快速排序, 参数A表示一个数组, start 表示开始索引, end 表示结束索引, 也就是对子数组 A[start, end] 进行快速排序算法 QuickSort(A, start, end) if start >= end return // 执行步骤1, 找到主元元素所在的位置 pivot = Partition(A, start, end) QuickSort(A, start, pivot - 1) QuickSort(A, pivot + 1, end) // 说明: 如果对数组 A 中的所有元素进行排序, 那么初始调用是 QuickSort(A, 0, A.length-1)。 // Partition(A, start, end) 是将数组分为三个部分 A[start, pivot-1], A[pivot] 和 A[pivot+1, r], 其中 A[start, pivot-1] 都比 A[pivot] 小, A[pivot+1, end] 都比 A[pivot] 大. Partition(A, start, end) // 选取第一个元素为主元 pivotKey = A[start] // 已经与主元元素对比过的分界位置, 左边是小于主元的元素, 右边是大于主元的元素 sep = start // 第一个元素是主元, 故从第二个元素开始逐个对比 for j = start + 1 to end if A[j] <= pivotKey // 左侧元素要增加一个 sep++ // 交换 A[sep] 和 A[j] 的位置, 将 A[j] 放在分界线的左侧 A[sep], A[j] = A[j], A[sep] // 最后将 A[start] 这个元素放在分界线的位置, 也就是 A[sep] 的位置 A[start], A[sep] = A[sep], A[start] return sep

3.3 算法演绎

快速排序算法理解起来稍微有些困难, 为了便于更简单的理解, 我们用一个具体的序列 $A=[4,1,5,8,3]$ 演绎一下快速排序算法的执行步骤.

对 A[0, 4]= [4, 1, 8, 5, 3] 执行快速排序算法

此时参数 A = [4, 1, 5, 8, 3], start=0, end=4 由于 start < end, 进入算法 1. 首先执行 Partition(A, 0, 4), 选取第一个元素 A[0]=4 为主元, 即 pivotKey=4, 并将此元素和数组中的所有元素对比, 初始 sep=0: (1) 当 j=1 时, 比较 pivotKey=4 与 A[1] = 1, 知 4 > 1, 此时 sep++ 也变为 1, 将 A[1] 与 A[1] 位置交换, A 不变; (2) 当 j=2 时, 比较 pivotKey=4 与 A[2]=5, 知 4 < 5, A 不变; (3) 当 j=3 时, 比较 pivotKey=4 与 A[3]=8, 知 4 < 8, A 不变, A = [4, 1, 5, 8, 3]; (4) 当 j=4 时, 比较 pivotKey=4 与 A[4]=3, 知 4 > 3, 此时 sep++ 变为 2, 接着将 A[2] 与 A[4] 交换位置, 此时 A=[4, 1, 3, 8, 5], 退出循环; (5) 此时 sep=2, 将 A[0] 与 A[2] 交换位置, 此时 A = [3, 1, 4, 8, 5]; (6) 最终返回 sep=2, 此时可以看出 A[2] = 4 前面的元素都比 4 小, 后面的元素都比 4 大; 2. 对 A[0, 1] = [3, 1] 和 A[3, 4] = [8, 5] 进行快速排序, 重复上述步骤.

图形演示如下:

说明:

选取第一个元素为主元 $pivotKey=A[start]$;

浅阴影部分的数组元素都比 $pivot$ 小, 深阴影部分的数字组元素都比 $pivot$ 大, 无阴影部分是还未进行划分的元素(除去第一个元素);

在 第(6)步中, 将 $A[pivot]$ 与 $A[sep]$ 交换, 此时 $A[sep]$ 左侧的元素都比它小, 右侧的元素都比它大。

对A[0, 1] = [3, 1] 执行快速排序算法

此时参数 A = [3, 1, 4, 8, 5], start=0, end=1 由于 start < end, 进入算法 1. 首先执行 Partition(A, 0, 1), 选取第一个元素 A[0]=3 为主元, 即 pivotKey=3, 并将此元素和数组中的所有元素对比, 初始 sep = 0: (1) 当 j=1 时, 比较 pivotKey=3 与 A[1]=1, 知 3 > 1, 此时 sep++ 也为 1, 接着将 A[1] 与 A[1] 位置交换, A 不变, 退出循环; (2) 此时 sep=1, 将 A[0] 与 A[1] 交换位置, 此时 A = [1, 3, 4, 8, 5]; (3) 最终返回 sep=1; 2. 对 A[0, 0] = [1] 再次进行快速排序, 实际上会直接退出, 不会进入算法.

这一步比较简单, 所以就不在提供图形演示了, 只要理解了上面图形演示, 拿这一步就很简单了。

对A[3, 4] = [8, 5] 执行快速排序算法

此时参数 A = [1, 3, 4, 8, 5], start=3, end=4 由于 start < end, 进入算法 1. 首先执行 Partition(A, 3, 4), 选取第一个元素 A[3]=8 为主元, 即 pivotKey=8, 并将此元素和数组中的所有元素对比, 初始 sep=3: (1) 当 j=4 时, 比较 pivotKey=8 与 A[4]=5, 知 8 > 5, 此时 sep++ 也是 4, 接着 将 A[4] 与 A[4] 位置交换, A 不变, 退出循环; (3) 此时 sep=4, 将 A[3] 与 A[4] 交换位置, 此时 A = [1, 3, 4, 5, 8]; (4) 最终返回 sep = 4; 2. 对 A[3, 3] = [5] 再次进行快速排序, 实际上会直接退出, 不会进入算法, 排序结束.

3.4 算法实现

我们今天用 JavaScript 实现以下快速排序的算法

// QuickSort(A, start, end) 快速排序, 参数A表示一个数组, start 表示开始索引, end 表示结束索引, 也就是对子数组 A[start, end] 进行快速排序算法 function QuickSort(A, start, end) { if (start >= end) return A; pivot = Partition(A, start, end); QuickSort(A, start, pivot - 1); QuickSort(A, pivot + 1, end); return A; } function Partition(A, start, end) { var pivotKey = A[start]; var sep = start; for (var j = start + 1; j <= end; j++) { if (A[j] < pivotKey) { sep++; var tmp = A[sep]; A[sep] = A[j]; A[j] = tmp; } } var tmp = A[start]; A[start] = A[sep]; A[sep] = tmp; return sep; } // 算法测试, 通过调试可以清楚的看到上面的算法演绎的过程 A = [4, 1, 5, 8, 3] // 调用方式 console.log(QuickSort(A, 0, A.length-1));

3.5 时间复杂度

由于快速排序的时间复杂度分析设计到专业的数学知识, 以后可能会专门出一篇文章进行详细的分析, 在这里不过多赘述。其实快速排序算法的时间复杂度主要取决于每次执行 Partition 时数组如何划分：

**最坏情况划分： ** 当划分产生的两部分分别包含 n-1 个元素 和 0 个元素时， 就是最坏情况， 那在执行划分过程时， 需要循环 n-1 次， 假设每次都是这种情况， 那共需要循环 $$1+2+...+(n-1)=n\ast (n-1)/2$$

此时时间复杂度还是 $O(n^2)$ 。

**最好情况划分： ** 最理想的情况， 就是每次划分都是平均的， 也就是一半的元素小于主元， 一半的元素大于主元， 此时时间复杂度就是 $O(nlgn)$。

**平均情况： ** 快速排序的平均情况更接近于最好情况， 所以只要每次划分的两部分是常数比例， 算法的时间复杂度就还是 $O(nlgn)$。

​ 综上所述, 快速排序的平均时间复杂度是 $O(nlgn)$, 这个时间复杂度远小于 $O(n^2)$， 也就是说 快速排序 在大多数情况下都是优于 冒泡排序 或者 插入排序 的， 这也是为什么很多家公司面试时必问快速排序算法的原因。在本系列的下一篇文章中， 我们将介绍其他常见的排序算法 —— 归并排序算法并分析其时间复杂度。