排序问题和排序算法

1. Introduction

排序算法将一串数组(一个列表)中的元素(整数,数字,字符串等)按某种顺序(增大,减小,字典顺序等)重新排列。
有很多种不同的排序算法,每一种都有各自的优势和限制。
排序常常作为计算机课程中的介绍性问题,用以介绍一系列的算法思路。
不失普遍性,我们在此可视化中,只将(可能包含重复)的整数数组排序至非减。试试点击 Bubble Sort 来可视化五个(含重复项)的杂乱整数的排序。

1-1. 动力 - 有趣的计算机科学想法

排序问题有许多有趣的算法解决方案,体现了许多计算机科学的思想:

  1. 比较非比较的策略,
  2. 迭代与递归实现,
  3. 分治范式(例如,归并排序快速排序),
  4. 最好/最坏/平均时间复杂度分析,
  5. 随机算法等。

1-2. 动力 - 应用

当(整数)数组 A 有序时,涉及 A 的许多问题变得简单(至少比原本简单):
  1. 在数组 A 中搜索特定值 v
  2. 查找(静态)数组 A 中的最小/最大/第 k 个最小/最大值,
  3. 测试唯一性并删除数组 A 中的重复项,
  4. 计算特定值 v 在数组 A 中出现多少次,
  5. 设置数组 A 和另一个排序数组 B 之间的交集/联合,
  6. 寻找一个目标对 x∈Ay∈A,使得 x + y 等于目标 z 等。
  7. 计算在区间 [lo..hi] 内共计有多少个值。
讨论:在现实课堂中,指导员可以详细阐述这些应用。

1-3. 小提示

[This is a hidden slide]

2. 动作

在这个可视化中,你可以做两件事。

2-1. 定义你自己的输入

第一步是关于定义你自己的输入,一个数组/一个列表是:
  1. 完全随机的
  2. 随机但有序的(按升序/降序排列)
  3. 随机但几乎有序的(按升序/降序排列)
  4. 随机但包含许多重复项(因此在小范围的整数内)
  5. 完全由你自己定义。
在探索模式下,您可以尝试使用此可视化中提供的各种排序算法来找出最佳和最差情况的输入。

2-2. 执行已选择的排序算法

第二个操作是最重要的操作:通过单击“Sort”按钮来执行排序算法。

需要注意的是,你可以通过切换页面顶部的算法缩写来切换当前算法。

3. 可视化

在此处查看所选排序算法的可视化/动画。
不失一般性,我们在可视化中只展示整数,而我们的目标是把它们从初始数列排序至非减数列。需要注意的是,非减数列绝大多数情况下意味着递增数列,但是存在有重复元素的可能性,有可能相邻元素之间会相等。

4. 常见的排序算法

你能在顶部找到计算机课上常见的几种排序算法。你可以在点击“Sort”之前,通过选择相应的算法缩写来激活不同的算法。
为了使我们的课堂更多样,我们在页面加载时会随机选择一个算法。
这门课中前六个算法是基于排序的,而后两个不是。我们会在这个电子讲座中讨论这个想法。
中间的三个算法是递归的,而其他的算法常常基于迭代实现。

4-1. 缩写

为了节省屏幕空间,我们将算法名称缩写为三个字符:

  1. 基于比较的排序算法:
    1. BUB - 冒泡排序,
    2. SEL - 选择排序,
    3. INS - 插入排序,
    4. MER - 归并排序 (递归实现),
    5. QUI - 快速排序 (递归实现),
    6. R-Q - 随机快速排序 (递归实现)
  2. 不基于比较的排序算法:
    1. COU - 计数排序,
    2. RAD - 基数排序

5. 3. O(N2) 基于比较的排序算法

在接下来的幻灯片,我们将讨论三种基于比较的排序算法

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
它们被称为基于比较的算法,因为它们比较数组的元素对并决定是否交换它们。
这三种排序算法最容易实现,但不是效率最高的,因为它们的时间复杂度是O(N2)。

6. 基础算法分析

在我们开始各种排序算法的讨论之前,或许先讨论渐进算法的分析能帮助你理解后面要提到的各种 O(N2),O(N log N),和特殊的 O(N) 的排序算法。
如果你对这方面知识已有了解,可跳过此小节。

6-1. 数学预备知识

你应该已经了解下列知识:
-. 对数和指数, e.g., log2(1024) = 10, 210 = 1024
-. 等差数列, e.g., 1+2+3+4+…+10 = 10*11/2 = 55
-. 等比数列, e.g., 1+2+4+8+..+1024 = 1*(1-211)/(1-2) = 2047
-. 线性/二次/三次函数, e.g., f1(x) = x+2, f2(x) = x2+x-1, f3(x) = x3+2x2-x+7
-. 向上取整 (ceiling), 向下取整 (floor) , 和绝对值 (absolute) 函数, e.g., ceil(3.1) = 4, floor(3.1) = 3, abs(-7) = 7

6-2. 是什么?

算法的分析是一个严谨分析算法所需资源(时间和空间)并用简单公式表示结果的过程。
算法所需的时间/空间也被分别称为算法的时间/空间复杂度。
在本课中,我们会更注重各排序算法的时间要求。

6-3. 测量实际运行时间?

我们可以通过使用墙钟时间或在我们的程序中插入时间测量代码来测量程序的实际运行时间,例如,参见 SpeedTest.cpp | py | java 中显示的代码。


然而,实际运行时间在比较两种算法时并没有意义,因为它们可能是用不同的语言编写的,使用不同的数据集,或在不同的计算机上运行。

6-4. 数操作数(1)

我们不是测量实际的时间,而是计算操作的数量(算术,赋值,比较等)。这是一种评估其效率的方法,因为算法的执行时间与它所需的操作数量有关。


请参阅在 SpeedTest.cpp | py | java 中显示的代码和评论(特别是如何获得变量计数器的最终值)。


知道算法需要的操作数量(精确),我们可以这样说:算法 X 需要 2n2 + 100n 次操作来解决大小为 n 的问题。

6-5. 数操作数(2)

如果已知一次操作所需的时间t,那么我们可以说算法X需要(2n2 + 100n)t时间单位来解决大小为n的问题。


然而,时间t取决于前面提到的因素,例如,不同的语言、编译器和计算机,操作本身的复杂性(加法/减法比乘法/除法更容易/更快地计算),等等。


因此,我们可以说,算法X解决大小为n的问题所需的时间与2n2 + 100n成比例,而不是将分析与实际时间t绑定在一起。

6-6. 渐进分析

渐近分析是一种专注于分析大输入大小n问题的算法分析,只考虑公式的主导项,并忽略主导项的系数


我们选择主导项,因为随着输入的增大,低阶项对总体成本的贡献较小,例如,对于f(n) = 2n2 + 100n,我们有:
f(1000) = 2*10002 + 100*1000 = 2.1M,相比之下
f(100000) = 2*1000002 + 100*100000 = 20010M。
(注意,低阶项100n的贡献较小)。

6-7. 忽略首项的系数

假设两个算法分别有 2n2 and 30n2 的首项。
虽然实际时间会因常数不同而不同,但它们的增长率 (growth rate) 是一样的。
相比于另一个首项为 n3 的算法,增长率的不同才是更重要的决定因素。
因此,我们在学习算法复杂度的时候可以不用在意首项的系数。

6-8. 上限(Big-O 符号)

如果算法 A 需要正比于 f(n) 的时间,则算法 A 和 f(n) 等阶。

写作算法 A 有时间复杂度 O(f(n)),其中 f(n) 是算法 A 的增长率函数。

6-9. Big-O 符号(数学上的)

数学上来说,对于一个算法 A ,当存在常数 k,正整数 n0 使得 A 解决大小为 n (n ≥ n0) 的问题时话费的时间不超过 k*f(n),那么我们认为 A 是一个 O(f(n)) 的算法。也就是说,当问题大小大于 n0,算法 A 不超过 k*f(n) 时间。

注意:n0k 不唯一,可能存在很多可能的有效 f(n)

6-10. 增长项

在渐进分析 (asymptotic analysis) 中,一个公式能被简化为系数为1的单项。
这一项被称为增长项 (growth term),其中包含了增长率 (rate of growth),增长次幂 (order of growth),数量级(order of magnitude) 信息。
最常见的增长项从快到慢依次是:
O(1)/常数时间 < O(log n)/对数时间 < O(n)/线性时间 < O(n log n)/准线性时间 < O(n2)/二次时间 < O(n3)/三次时间 <
O(2n)/指数时间 < O(n!)/同样指数时间 < ∞ (如死循环).

6-11. 增长项(可视化的/比较的)

我们在接下来的排序课程中会看到三种不同的增长率:O(n2), O(n log n), 和 O(n)。

7. 冒泡排序

给定一个 N 个元素的数组,冒泡法排序将:
  1. 比较一对相邻元素(a,b),
  2. 如果两项的大小关系不正确,交换这两个数(在本例中为a > b),
  3. 重复步骤1和2,直到我们到达数组的末尾(最后一对是第 N-2 N-1 项,因为我们的数组从零开始)
  4. 到目前为止,最大项将在最后的位置。 然后我们将 N 减少1,并重复步骤1,直到 N = 1
不用多说,我们来试试上面的小例子 Bubble Sort
如果您想象较大的项目“冒泡”(也就是“浮动到数组的右侧”),则应该能看到到一个“气泡式”动画。

7-1. 冒泡排序,伪代码 & 分析

method bubbleSort(array A, integer N) // 标准版本
for each R from N-1 down to 1 // 重复 N-1 次迭代
for each index i in [0..R-1] // '未排序区域',O(N)
if A[i] > A[i+1] // 这两个不是非递减顺序
swap(a[i], a[i+1]) // 在 O(1) 中交换它们

比较和交换需要的时间由一个常数限制,我们称之为 c。然后,在(标准)冒泡排序中有两个嵌套循环。外循环正好运行 N-1 次迭代。但是内循环的运行时间越来越短:

  1. 当 R=N-1 时,(N−1) 次迭代(比较和交换),
  2. 当 R=N-2 时,(N−2) 次迭代,
    ...,
  3. 当 R=1 时,1 次迭代(然后完成)。

因此,总的迭代次数 = (N−1)+(N−2)+...+1 = N*(N−1)/2 (推导).

总时间 = c*N*(N−1)/2 = O(N^2).


请参阅在 SortingDemo.cpp | py | java 中显示的代码。

7-2. 冒泡排序:提前终止

冒泡排序实际上效率低下,其O(N^2)时间复杂度。想象一下,我们有N = 105个数字。即使我们的计算机超级快,能在1秒内计算108次操作,冒泡排序也需要大约100秒才能完成。


然而,它可以提前终止,例如,在上面显示的小型升序排序示例 [3, 6, 11, 25, 39]中,Bubble Sort可以在O(N)时间内终止。


改进的想法很简单:如果我们在内循环中没有交换,那就意味着数组已经排序,我们可以在那个点停止冒泡排序。


讨论:尽管这使冒泡排序在一般情况下运行得更快,但这个改进的想法并没有改变冒泡排序的O(N^2)时间复杂度...为什么呢?

7-3. 答案

[This is a hidden slide]

8. 选择排序

给定 N 个项目和 L = 0 的数组,选择排序将:
  1. [L ... N-1] 范围内找出最小项目 X 的位置,
  2. 用第 L 项交换第 X 项,
  3. 将下限 L 增加1并重复步骤1直到 L = N-2
让我们在上面的同一个小示例数组上尝试 Selection Sort
在不失普遍性的情况下,我们也可以实现反向的选择排序:找到最大项目 Y 的位置并将其与末项交换。

8-1. 选择排序,伪代码 & 分析

method selectionSort(array A[], integer N)
for each L in [0..N-2] // O(N)
let X be the index of the minimum element in A[L..N-1] // O(N)
swap(A[X], A[L]) // O(1),X 可能等于 L (没有实际交换)

总计: O(N2) — 准确地说,它类似于冒泡排序分析


请参阅在SortingDemo.cpp | py | java中显示的代码。

8-2. 小测验

Quiz: How many (real) swaps are required to sort [29, 10, 14, 37, 13] by Selection Sort?

4
2
3
1

9. 插入排序

插入排序类似于大多数人整理扑克牌的方式。Poker hand

  1. 手里只拿一张牌,
  2. 拿下一张牌并将其插入到正确的排序位置,
  3. 对所有牌重复上一步。

让我们尝试在小示例数组 [40, 13, 20, 8] 上使用 Insertion Sort

9-1. 插入排序,伪代码和分析 1

method insertionSort(array A[], integer N)
for i in [1..N-1] // O(N)
let X be A[i] // X is the next item to be inserted into A[0..i-1]
for j from i-1 down to 0 // this loop can be fast or slow
if A[j] > X
A[j+1] = A[j] // make a place for X
else
break
A[j+1] = X // insert X at index j+1

See the code shown in SortingDemo.cpp | py | java.

9-2. 插入排序:分析 2

外循环执行 N-1 次,这很明显。
但内循环执行的次数取决于输入:
  1. 在最好的情况下,数组已经排序并且 (a [j]> X) 总是为假。所以不需要移位数据,并且内部循环在O(1)时间内运行,
  2. 在最坏的情况下,数组被反向排序并且 (a [j]> X) 总是为真。插入始终发生在数组的前端,并且内部循环在O(N)时间内运行。
因此,最佳情况时间是O(N × 1) = O(N,最坏情况时间是O(N × N) = O(N2).

9-3. 小测验

Quiz: What is the complexity of Insertion Sort on any input array?

O(N^2)
O(N log N)
O(N)
O(1)

如果你对这个还不是很清楚,请教你的指导员或者在这个页面阅读相关的评述。

10. 2.5 O(N log N) 基于比较的排序

我们将在接下来的几张幻灯片中讨论两种基于比较的排序算法:

  1. 归并排序
  2. 快速排序和它的随机版本(只有一个变化)。
这些排序算法通常以递归方式实现,使用分而治之的问题解决范例,并且只需 O(N log N) 的时间来运行归并排序,只需 O(N log N) 的时间期望运行随机快速排序。
PS:尽管如此,非随机版本的快速排序(Quick Sort)需要 O(N2) 时间来运行

11. 归并排序

给定一个 N 个项目的数组,归并排序将:
  1. 将每对单个元素(默认情况下,已排序)归并为2个元素的有序数组,
  2. 将2个元素的每对有序数组归并成4个元素的有序数组,重复这个过程......,
  3. 最后一步:归并2个N / 2元素的排序数组(为了简化讨论,我们假设N是偶数)以获得完全排序的N个元素数组。
这只是一般的想法,在我们可以讨论归并排序的真正形式之前,我们需要更多的细节。

11-1. 重要的子程序,O(N) 归并

我们首先从归并排序算法的最重要的子程序 -- O(N) 归并来剖析这个归并排序算法。
给定两个大小分别为 N1N2 的排序数组 A B,我们可以在O(N) 时间内将它们有效地归并成一个大小为 N = N1 + N2的组合排序数组。
这是通过简单地比较两个数组的首项并始终取两个中较小的一个来实现的。 但是,这个简单但快速的O(N)合并子程序将需要额外的数组来正确合并。

11-2. 合并子程序伪代码实现

method merge(array A, integer low, integer mid, integer high)
// 子数组1 = a[low..mid], 子数组2 = a[mid+1..high], 都已排序
int N = high-low+1
create array B of size N // 讨论:为什么我们需要一个临时数组b?
int left = low, right = mid+1, bIdx = 0
while (left <= mid && right <= high) // 合并过程
if (A[left] <= A[right])
B[bIdx++] = A[left++]
else
B[bIdx++] = A[right++]
while (left <= mid)
B[bIdx++] = A[left++] // 剩余部分,如果有的话
while (right <= high)
B[bIdx++] = A[right++] // 剩余部分,如果有的话
for (int k = 0; k < N; ++k)
A[low+k] = B[k]; // 复制回去

尝试在示例数组 [1, 5, 19, 20, 2, 11, 15, 17] 上使用 Merge Sort,该数组的前半部分已经排序 [1, 5, 19, 20],其后半部分也已经排序 [2, 11, 15, 17]。请集中注意力在归并排序算法的最后一次合并。

11-3. 分而治之的范例

在我们继续之前,让我们先谈谈分而治之(Divide and Conquer,缩写为D&C),这是一个强大的解决问题的范例。
分而治之算法通过以下步骤解决(某种类型的)问题 - 比如我们的排序问题:
  1. 划分步骤:将大的原始问题划分成较小的子问题并递归地解决较小的子问题,
  2. 解决步骤:结合较小的子问题的结果来解决较大的原始问题。

11-4. 归并排序是分而治之的算法

归并并排序是分而治之的排序算法。
划分步骤很简单:将当前数组分成两半(如果 N 是偶数,则将其完全平等,或者如果 N 是奇数,则一边多一项),然后递归地对这两半进行排序。
解决步骤是主要的工作:使用前面讨论的归并子程序合并两个(排序的)半部分以形成一个有序数组。

11-5. 归并排序伪代码实现

method mergeSort(array A, integer low, integer high)
// 要排序的数组是 A[low..high]
if (low < high) // 基本情况:low >= high (0 或 1 个项目)
int mid = (low+high) / 2
mergeSort(a, low , mid ) // 分成两半
mergeSort(a, mid+1, high) // 然后递归排序它们
merge(a, low, mid, high) // 征服:合并子程序

请参阅在SortingDemo.cpp | py | java中显示的代码。

11-6. 示范

与许多其他CS打印的教科书通常显示的相反(因为教科书是静态的),归并排序的实际执行不会一层一层地分成两个子数组,而是会在处理正确的子数组之前递归地排序左边的子数组。
就是这样,在示例数组 [7, 2, 6, 3, 8, 4, 5] 上尝试Merge Sort,它将递归计算 [7, 2, 6, 3],然后是 [7, 2],然后是 [7](单个元素,默认排序),回溯,递归到 [2](默认排序),回溯,然后在继续处理 [6, 3] 等等之前,将 [7, 2] 合并到 [2, 7] 中。

11-7. 归并排序:分析 第一部分

在归并排序中,大部分工作是在解决/归并的步骤中完成的,因为分解步骤并没有真正执行任何操作(视为O(1))。
当我们调用 merge(a, low, mid, high)的时候,我们处理 k = high - low + 1 项。 最多会有 k-1 次比较。 从原始数组 a 到临时数组 b k 次移动,而又有 k 次从 b 移回 a。 总的来说,归并子例程内的操作次数 < 3k-1 = O(k)。
重要的问题是这个 merge(归并)子程序被调用了多少次?

11-8. 归并排序:分析 第二部分

The Recursion Tree of Merge Sort

11-9. 归并排序:分析 第三部分

第一层:20 = 1 次调用 merge( ),每次包含 N / 21 个项目,时间复杂度 O(20 x 2 x N / 21)= O(N)
第二层:21 = 1 次调用 merge( ),每次包含 N / 22 个项目,时间复杂度 O(21 x 2 x N / 22)= O(N)
第三层:22 = 1 次调用 merge( ),每次包含 N / 23 个项目,时间复杂度 O(22 x 2 x N / 23)= O(N)
...
第 log N 层:2 ^(log N-1)(或N / 2)调用merge( ) ),其中N / 2 ^ log N(或1)个项目,O(N)
第 log N 层:2logN - 1 = 1 次调用 merge( ),每次包含 N / 2logN (或1)个项目,时间复杂度 O(22 x 2 x N / 23)= O(N)
共计有 log N 层,每层工作量都为 O(N) ,因此总体时间复杂度为 O(N log N)。 稍后我们会看到这是在基于比较的排序算法中最佳的一种,即我们无法做得比这更好。

11-10. 优缺点

无论输入的原始顺序如何,归并排序中最重要的部分是其O(N log N)性能保证。 就这样,没有任何针对性的测试用例可以使归并排序对于N个元素数组运行比O(N log N)更长的时间。
因此,归并排序非常适合大数组的排序,因为O(N log N)比前面讨论的O(N2)排序算法增长得慢得多。
然而,归并排序有几个不太好的部分。 首先,从零开始实现并不容易(虽然我们不必这样做)。 其次,它在归并操作期间需要额外的O(N)内存,因此会占用额外内存并且不是就地的 (in-place)。顺便说一句,如果你有兴趣看看为解决这些(经典)归并排序不那么好的部分做了什么,你可以阅读这个

归并排序也是一个稳定 (stable) 的排序算法。 讨论:为什么?

11-11. 答案

[This is a hidden slide]

12. 快速排序

快速排序是另一个分而治之的排序算法(另一个在这个可视化页面中讨论的是归并排序)。
在继续随机化和可用版本的快速排序之前,我们将看到,这种确定性的,非随机化的快速排序的版本可能在针对性输入中具有很差的 O(N2) 时间复杂度。

12-1. 快速排序是分而治之的算法

划分步骤:选择一个项目p(称为枢轴)
然后将A[i..j]的项目划分为三部分:A[i..m-1]A[m]A[m+1..j]
A[i..m-1](可能为空)包含小于(或等于)p的项目。
A[m] = p,即,索引m是数组a排序顺序中p的正确位置。
A[m+1..j](可能为空)包含大于(或等于)p的项目。
然后,递归排序这两部分。


征服步骤:别惊讶...我们什么都不做 :O!


如果你将这个与合并排序进行比较,你会发现快速排序的D&C步骤与合并排序完全相反。

12-2. 重要的子程序,O(N) 分区

我们将通过首先讨论其最重要的子程序:O(N) partition(经典版本)来剖析这个快速排序算法。


要划分A[i..j],我们首先选择A[i]作为枢轴p

剩余的项目(即,a[i+1..j])被划分为3个区域:

  1. S1 = A[i+1..m] 其中的项目 ≤ p
  2. S2 = A[m+1..k-1] 其中的项目 ≥ p,和
  3. 未知 = A[k..j],其中的项目尚未被分配到S1S2

讨论:为什么我们选择p = A[i]?还有其他选择吗?


更难的讨论:如果A[k] == p,我们应该将它放在区域S1还是S2?

12-3. 答案

[This is a hidden slide]

12-4. 分区排序 - 继续

最初,S1S2 区域都是空的,即所有除指定的轴心 p 之外的项目都在未知区域。


然后,对于未知区域中的每个项目 A[k],我们将 A[k]p 进行比较,并决定以下三种情况之一:

  1. 如果 A[k] > p,将 A[k] 放入 S2
  2. 如果 A[k] < p,将 A[k] 放入 S1
  3. 如果 A[k] == p,抛一枚硬币,如果硬币正面/反面落地,分别将 A[k] 放入 S1/S2

这三种情况将在接下来的两张幻灯片中详细说明。


最后,我们交换 A[i]A[m],将轴心 p 正好放在 S1S2 的中间。

12-5. 分区 - 当  A[k] > p 的情况

Case when a[k] ≥ p, increment k, extend S2 by 1 item

12-6. 分区 - 当  A[k] < p 的情况

Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item

12-7. 分区伪代码实现

int partition(array A, integer i, integer j)
int p = a[i] // p 是枢轴
int m = i // S1 和 S2 最初为空
for (int k = i+1; k <= j; ++k) // 探索未知区域
if ((A[k] < p) || ((A[k] == p) && (rand()%2 == 0))) { // 情况 2+3
++m
swap(A[k], A[m]) // 交换这两个索引
// 注意我们在情况 1: A[k] > p 时不做任何事情
swap(A[i], A[m]) // 最后一步,交换枢轴和 a[m]
return m // 返回枢轴的索引

12-8. 快速排序伪代码实现

method quickSort(array A, integer low, integer high)
if (low < high)
int m = partition(a, low, high) // O(N)
// A[low..high] ~> A[low..m–1], pivot, A[m+1..high]
quickSort(A, low, m-1); // 递归排序左子数组
// A[m] = pivot 在分区后已经排序
quickSort(A, m+1, high); // 然后排序右子数组

请参阅在SortingDemo.cpp | py | java中显示的代码。

12-9. 示范

尝试在示例数组 [27, 38, 12, 39, 29, 16] 上使用 Quick Sort。我们将详细说明第一步分区操作如下:
我们设定 p = A[0] = 27
我们设定 A[1] = 38 作为 S2 的一部分,所以 S1 = {}S2 = {38}
我们交换 A[1] = 38A[2] = 12,所以 S1 = {12}S2 = {38}
我们设定 A[3] = 39 和后来的 A[4] = 29 作为 S2 的一部分,所以 S1 = {12}S2 = {38,39,29}
我们交换 A[2] = 38A[5] = 16,所以 S1 = {12,16}S2 = {39,29,38}
我们交换 p = A[0] = 27A[2] = 16,所以 S1 = {16,12}p = {27},和 S2 = {39,29,38}


之后,A[2] = 27 保证已经排序,现在快速排序递归地首先排序左边的 A[0..1],然后递归地排序右边的 A[3..5]

12-10. 快速排序:分析 第一部分

首先,我们分析一次partition调用的成本。


partition(A, i, j)中,只有一个for循环,它迭代了(j-i)次。由于j可以大到N-1,i可以小到0,所以partition的时间复杂度是O(N)。


类似于归并排序分析,快速排序的时间复杂度则取决于partition(A, i, j)被调用的次数。

12-11. 快速排序:分析 第二部分

当数组A已经按升序排列,例如,A = [5, 18, 23, 39, 44, 50],Quick Sort 将设置p = A[0] = 5,并返回m = 0,从而使S1区域S2区域:除了枢轴(N-1 项)以外的所有其他内容。

12-12. 快速排序: 分析 第三部分

在这种最坏情况的输入场景下,会发生以下情况:


快速排序的最坏情况分析

第一次分区需要 O(N) 的时间,将 A 分为 0, 1, N-1 个项目,然后向右递归。
第二次分区需要 O(N-1) 的时间,将 A 分为 0, 1, N-2 个项目,然后再次向右递归。
...
直到最后,第 N 次分区将 A 分为 0, 1, 1 个项目,快速排序递归停止。


这是经典的 N+(N-1)+(N-2)+...+1 模式,它是 O(N2),与这个冒泡排序分析幻灯片中的分析类似...

12-13. 快速排序:最佳情况(极少)

当分区总是将数组分成两个相等的一半时,就会发生快速排序的最佳情况,如归并排序
当发生这种情况时,递归的深度只有 O(log N)。
由于每个级别进行 O(N) 比较,时间复杂度为 O(N log N)。
在这个手工制作的示例输入数组 [4, 1, 3, 2, 6, 5, 7] 上尝试Quick Sort。这在实践中很少见,因此我们需要设计一个更好的方法:随机快速排序

13. 随机快速排序

快速排序相同,除了在执行分区算法之前,它随机选择A[i..j]之间的枢轴,而不是总是确定性地选择A[i](或[i..j]之间的任何其他固定索引)。


小练习:将上述想法应用到这个幻灯片中显示的实现!


在这个大而有些随机的示例数组a = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]上运行 Random Quick Sort 感觉很快。

13-1. 魔法般的分析

要正确解释为什么这个随机版本的快速排序在任何包含N个元素的输入数组上的预期时间复杂度为O(N log N),大约需要1小时的讲座。


在这个电子讲座中,我们将假设这是正确的。


如果你需要非正式的解释:只需想象在随机化版本的快速排序中,我们随机选择枢轴,我们总是得到极其糟糕的分割,即0(空),1(枢轴),和N-1个其他项目。这种幸运(半枢轴半),有点幸运,有点不幸,和极其不幸(空,枢轴,其余)的组合产生了平均时间复杂度为O(N log N)。


讨论:对于Partition的实现,如果A[k] == p,我们总是确定性地将A[k]放在一侧(S1S2)会发生什么?

13-2. 答案

[This is a hidden slide]

14. 2. O(N) 不基于比较的排序算法

在接下来的幻灯片,我们将讨论两种不基于比较的排序算法:

  1. 计数排序,
  2. 基数排序.

这些排序算法可以不比较数组的项,从而比时间复杂度为 Ω(N log N)的基于比较的排序算法的下限更快。

14-1. 排序算法的下限

众所周知(尽管在这个可视化中并未证明,因为这需要大约半小时的决策树模型讲座才能做到),所有基于比较的排序算法的时间复杂度下界都是Ω(N log N)。


因此,任何具有最坏情况复杂度为O(N log N)的基于比较的排序算法,如Merge Sort,都被认为是最优算法,即我们不能做得比这更好。


然而,如果输入数组存在某些假设,我们可以实现更快的排序算法 — 即O(N) — 从而避免比较项目以确定排序顺序。

15. 计数排序

假设:如果要排序的项目是小范围的整数,我们可以计算每个整数(在这个小范围内)的出现频率,然后通过循环该小范围来有序输出各项。
用上面的 [1...9] 范围内的示例数组中尝试 Counting Sort,因此我们只需要计算整数1出现的次数,整数2出现的次数,...,整数9出现的次数,然后遍历1到9。如果整数 y 的频率为 x,则打印出整数 y x 个副本。
计算频率时间复杂度为 O(N),有序输出结果的时间复杂度为 O(N + k),其中 k 是输入的整数范围,在本例中为 9-1+1 = 9。计数排序(Counting Sort)的时间复杂度为 O(N + k),如果 k 很小,那么它就是 O(N)。
由于内存限制,当 k 相对较大时,我们将无法执行计数排序(Counting Sort)的计数部分,因为我们需要存储 k 个整数出现的次数。

16. 基数排序

假设:如果要排序的项目是具有大范围但少位数的整数,我们可以将计数排序的思想与基数排序相结合,以实现线性时间复杂度。


在基数排序中,我们将要排序的每个项目视为一个由w位数字组成的字符串(如果需要,我们会在位数少于w位的整数前面填充零)。


从最低有效位(最右边)到最高有效位(最左边),我们遍历N个项目,并根据当前位将它们放入10个队列中(每个数字[0..9]一个队列),这类似于一个修改过的计数排序,因为它保持了稳定性(请记住,之前在此幻灯片中展示的计数排序版本不是稳定排序)。然后我们再次将这些组重新连接起来进行后续迭代。


尝试在上面的随机4位数数组上点击 Radix Sort 以获得更清晰的解释。


请注意,我们只执行了O(w × (N+k))次迭代。在这个例子中,w = 4k = 10

16-1. 最好的整数排序算法?

现在,我们已经讨论过基数排序,那么我们应该在每一个排序情况下使用它吗?


例如,理论上来说,对许多(N非常大)32位有符号整数进行排序应该更快,因为w ≤ 10位数,k = 10,如果我们将这些32位有符号整数解释为十进制。O(10 × (N+10)) = O(N)。


讨论:如本可视化所示,使用基数10实际上并不是排序N个32位有符号整数的最佳方式。那么更好的设置应该是什么呢?

16-2. 答案

[This is a hidden slide]

17. 排序算法的附加属性

除了比较还是非比较,递归还是迭代之外,还有其他一些属性可用于区分排序算法。
在本节中,我们将讨论就地(in-place)与非就地,稳定 (stable) 与不稳定以及高速缓存的排序算法的性能。

17-1. 就地 (in-place) 排序

如果一个排序算法在排序过程中只需要常量级别(即,O(1))的额外空间,那么我们就说这是一个原地排序算法。也就是说,少量的、常数个数的额外变量是可以的,但我们不允许有依赖于输入大小N的变量长度。


归并排序(经典版本),由于其merge子程序需要额外的临时数组,大小为N,所以它不是原地排序。


讨论:冒泡排序、选择排序、插入排序、快速排序(是否随机)、计数排序和基数排序,哪些是原地排序?

17-2. 稳定 (stable) 排序

如果排序算法在排序执行后保留了具有相同键值的元素的相对顺序,那么这种排序算法被称为稳定(stable)


稳定排序的示例应用:假设我们有按字母顺序排序的学生名字。现在,如果这个列表再次按照教学小组编号排序(回想一下,一个教学小组通常有很多学生),一个稳定的排序算法会确保同一个教学小组的所有学生仍然按照他们的名字的字母顺序出现。基数排序需要通过多轮按位排序,并需要一个稳定的排序子程序才能正确工作。


讨论:在这个电子讲座中讨论的排序算法中,哪些是稳定的?
尝试对数组 A = {3, 4a, 2, 4b, 1} 进行排序,即有两个4的副本(先是4a,然后是4b)。

17-3. 缓存性能

[This is a hidden slide]

18. 小测验

我们的电子课堂接近尾声了。
小测验时间!

18-1. 小测验 #1

Quiz: Which of these algorithms run in O(N log N) on any input array of size N?

Bubble Sort
Insertion Sort
Merge Sort
Quick Sort (Deterministic)

18-2. 小测验 #2

Quiz: Which of these algorithms has worst case time complexity of Θ(N^2) for sorting N integers?

Insertion Sort
Selection Sort
Bubble Sort
Merge Sort
Radix Sort
Θ是一个紧 (tight) 的时间复杂度分析,其中最佳情况 Ω 和最坏情况的 big-O 分析互相匹配。

19. 附加功能

我们已经到了电子讲座 - 排序的末尾。
但是,VisuAlgo 中还有另外两种嵌入在其他数据结构中的排序算法:堆排序平衡BST排序。 我们将在这两种数据结构的电子讲座里面讨论它们。

19-1. 挑战

[This is a hidden slide]

19-2. 逆序数 / 逆序数对的个数

[This is a hidden slide]

19-3. 实现方法

实际上,许多这些基本排序算法的C ++源代码已经分散在这些电子讲座幻灯片中。对于其他编程语言,您可以将给定的C ++源代码翻译为其他编程语言。
通常,排序只是问题解决过程中的一小部分,而现在大多数编程语言都有自己的排序函数,所以非必要情况,我们不需要复现其代码。
在C++中,您可以使用STL算法中的std::sortstd::stable_sortstd::partial_sort

在Java中,您可以使用Collections.sort

在Python中,您可以使用sort

在OCaml中,您可以使用List.sort compare list_name
如果比较函数是针对特定问题的,我们可能需要为这些内置的排序例程提供额外的比较函数。

19-4. 在线测验

是时候检验你对于这些排序算法的基础的掌握程度了!
Test your understanding here!

19-5. 在线评估练习

现在您已经到了电子讲座的最后部分,您认为排序问题与调用内置的排序程序一样简单吗?
尝试这些在线评判问题以了解更多信息:
Kattis - mjehuric
Kattis - sortofsorting,或者
Kattis - sidewayssorting
这不是排序算法的结束。 当您在 VisuAlgo 中探索其他主题时,您会意识到排序是许多其他高难度问题的高级算法的预处理步骤,例如, 作为克鲁斯卡尔算法(Kruskal's algorithm)的预处理步骤,创造性地用于后缀数组 (Suffix Array) 数据结构等。

20. Detailed Analysis of Randomized Quicksort


start of 3230 material