>

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

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

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

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

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑
当(整数)数组 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] 内共计有多少个值。
讨论:在现实课堂中,指导员可以详细阐述这些应用。

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

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

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

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

🕑
在此处查看所选排序算法的可视化/动画。
不失一般性,我们在可视化中只展示整数,而我们的目标是把它们从初始数列排序至非减数列。需要注意的是,非减数列绝大多数情况下意味着递增数列,但是存在有重复元素的可能性,有可能相邻元素之间会相等。
🕑
你能在顶部找到计算机课上常见的几种排序算法。你可以在点击“Sort”之前,通过选择相应的算法缩写来激活不同的算法。
为了使我们的课堂更多样,我们在页面加载时会随机选择一个算法。
这门课中前六个算法是基于排序的,而后两个不是。我们会在这个电子讲座中讨论这个想法。
中间的三个算法是递归的,而其他的算法常常基于迭代实现。
🕑

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

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

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

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
它们被称为基于比较的算法,因为它们比较数组的元素对并决定是否交换它们。
这三种排序算法最容易实现,但不是效率最高的,因为它们的时间复杂度是O(N2)。
🕑
在我们开始各种排序算法的讨论之前,或许先讨论渐进算法的分析能帮助你理解后面要提到的各种 O(N2),O(N log N),和特殊的 O(N) 的排序算法。
如果你对这方面知识已有了解,可跳过此小节。
🕑

你应该已经了解下列知识:
-. 对数和指数, 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

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

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


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

🕑

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


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


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

🕑

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


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


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

🕑

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


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

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

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

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

注意:n0k 不唯一,可能存在很多可能的有效 f(n)
🕑
在渐进分析 (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!)/同样指数时间 < ∞ (如死循环).
🕑
我们在接下来的排序课程中会看到三种不同的增长率:O(n2), O(n log n), 和 O(n)。
🕑
给定一个 N 个元素的数组,冒泡法排序将:
  1. 比较一对相邻元素(a,b),
  2. 如果两项的大小关系不正确,交换这两个数(在本例中为a > b),
  3. 重复步骤1和2,直到我们到达数组的末尾(最后一对是第 N-2 N-1 项,因为我们的数组从零开始)
  4. 到目前为止,最大项将在最后的位置。 然后我们将 N 减少1,并重复步骤1,直到 N = 1
不用多说,我们来试试上面的小例子 Bubble Sort
如果您想象较大的项目“冒泡”(也就是“浮动到数组的右侧”),则应该能看到到一个“气泡式”动画。
🕑
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 中显示的代码。

🕑

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


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


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


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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

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

🕑

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

3
4
2
1

🕑

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

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

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

🕑
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.

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

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

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

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

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

  1. 归并排序
  2. 快速排序和它的随机版本(只有一个变化)。
这些排序算法通常以递归方式实现,使用分而治之的问题解决范例,并且只需 O(N log N) 的时间来运行归并排序,只需 O(N log N) 的时间期望运行随机快速排序。
PS:尽管如此,非随机版本的快速排序(Quick Sort)需要 O(N2) 时间来运行
🕑
给定一个 N 个项目的数组,归并排序将:
  1. 将每对单个元素(默认情况下,已排序)归并为2个元素的有序数组,
  2. 将2个元素的每对有序数组归并成4个元素的有序数组,重复这个过程......,
  3. 最后一步:归并2个N / 2元素的排序数组(为了简化讨论,我们假设N是偶数)以获得完全排序的N个元素数组。
这只是一般的想法,在我们可以讨论归并排序的真正形式之前,我们需要更多的细节。
🕑
我们首先从归并排序算法的最重要的子程序 -- O(N) 归并来剖析这个归并排序算法。
给定两个大小分别为 N1N2 的排序数组 A B,我们可以在O(N) 时间内将它们有效地归并成一个大小为 N = N1 + N2的组合排序数组。
这是通过简单地比较两个数组的首项并始终取两个中较小的一个来实现的。 但是,这个简单但快速的O(N)合并子程序将需要额外的数组来正确合并。
🕑
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]。请集中注意力在归并排序算法的最后一次合并。

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

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

🕑
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中显示的代码。

🕑
与许多其他CS打印的教科书通常显示的相反(因为教科书是静态的),归并排序的实际执行不会一层一层地分成两个子数组,而是会在处理正确的子数组之前递归地排序左边的子数组。
就是这样,在示例数组 [7, 2, 6, 3, 8, 4, 5] 上尝试Merge Sort,它将递归计算 [7, 2, 6, 3],然后是 [7, 2],然后是 [7](单个元素,默认排序),回溯,递归到 [2](默认排序),回溯,然后在继续处理 [6, 3] 等等之前,将 [7, 2] 合并到 [2, 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(归并)子程序被调用了多少次?
🕑
The Recursion Tree of Merge Sort
🕑
第一层: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)。 稍后我们会看到这是在基于比较的排序算法中最佳的一种,即我们无法做得比这更好。
🕑

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

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

划分步骤:选择一个项目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步骤与合并排序完全相反。

🕑

我们将通过首先讨论其最重要的子程序: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?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

最初,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 的中间。

🕑
Case when a[k] ≥ p, increment k, extend S2 by 1 item
🕑
Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item
🕑
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 // 返回枢轴的索引
🕑
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中显示的代码。

🕑

尝试在示例数组 [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]

🕑

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


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


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

🕑

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

🕑

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


快速排序的最坏情况分析

第一次分区需要 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),与这个冒泡排序分析幻灯片中的分析类似...

🕑

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

🕑

快速排序相同,除了在执行分区算法之前,它随机选择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 感觉很快。

🕑

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


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


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


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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

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

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

🕑

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


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


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

🕑
假设:如果要排序的项目是小范围的整数,我们可以计算每个整数(在这个小范围内)的出现频率,然后通过循环该小范围来有序输出各项。
用上面的 [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 个整数出现的次数。
🕑

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


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


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


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


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

🕑

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


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


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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

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

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


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


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

🕑

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


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


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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

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

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

Bubble Sort
Merge Sort
Insertion Sort
Quick Sort (Deterministic)

🕑

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

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

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

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

在Python中,您可以使用sort

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

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

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

🕑

start of 3230 material

🕑

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

0 1 2 3 4 5 6 7 8 9 A B C D E F

新建(A)

排序

>
N =

随机

已完成排序的

接近完成排序的

Many Duplicates

A =

前进

Set base

Set base

关于 团队 使用条款
隐私政策

关于

VisuAlgo最初由副教授Steven Halim于2011年构思,旨在通过提供自学、互动式学习平台,帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年,VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

虽然VisuAlgo主要面向新加坡国立大学(NUS)的学生,包括各种数据结构和算法课程(例如CS1010/等价课程,CS2040/等价课程(包括IT5003),CS3230,CS3233和CS4234),但它也是全球好奇心的宝贵资源,促进在线学习。

最初,VisuAlgo并不适用于智能手机等小触摸屏,因为复杂的算法可视化需要大量的像素空间和点击拖动交互。为了获得最佳用户体验,建议使用最低分辨率为1366x768的屏幕。然而,自2022年4月以来,VisuAlgo的移动(精简)版本已经推出,使得在智能手机屏幕上使用VisuAlgo的部分功能成为可能。

VisuAlgo仍然在不断发展中,正在开发更复杂的可视化。目前,该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器,其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成,并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统,它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重,计算机科学教师可以显著提高学生对这些基本概念的掌握程度,因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言:英语、中文和印尼语。此外,我们还用各种语言撰写了关于VisuAlgo的公开笔记,包括印尼语、韩语、越南语和泰语:

id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1
CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1
Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2
CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

本科生研究人员 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

最后一年项目/ UROP学生 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

致谢
NUS教学与学习发展中心(CDTL)授予拨款以启动这个项目。在2023/24学年,Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

使用条款

VisuAlgo慷慨地向全球计算机科学界提供免费服务。如果您喜欢VisuAlgo,我们恳请您向其他计算机科学学生和教师宣传它的存在。您可以通过社交媒体平台(如Facebook、YouTube、Instagram、TikTok、Twitter等)、课程网页、博客评论、电子邮件等方式分享VisuAlgo。

数据结构与算法(DSA)的学生和教师可以直接在课堂上使用本网站。如果您从本网站截取屏幕截图或视频,可以在其他地方使用,但请引用本网站的URL(https://visualgo.net)和/或下面的出版物列表作为参考。但请不要下载VisuAlgo的客户端文件并将其托管在您的网站上,因为这构成了抄袭行为。目前,我们不允许他人分叉此项目或创建VisuAlgo的变体。个人使用离线副本的客户端VisuAlgo是可以接受的。

请注意,VisuAlgo的在线测验组件具有重要的服务器端元素,保存服务器端脚本和数据库并不容易。目前,普通公众只能通过“培训模式”访问在线测验系统。“测试模式”提供了一个更受控制的环境,用于在新加坡国立大学的真实考试中使用随机生成的问题和自动验证。


出版物列表

这项工作曾在2012年国际大学生程序设计竞赛(波兰,华沙)的CLI研讨会上和2012年国际信息学奥林匹克竞赛(意大利,锡尔米奥内-蒙蒂基亚里)的IOI会议上展示过。您可以点击此链接阅读我们2012年关于该系统的论文(当时还没有称为VisuAlgo),以及此链接阅读2015年的简短更新(将VisuAlgo与之前的项目关联起来)。


错误报告或新功能请求

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误,或者您想要请求新功能,请联系Steven Halim副教授。他的联系方式是将他的名字连接起来,然后加上gmail dot com。

隐私政策

版本 1.2 (更新于2023年8月18日星期五)。

自2023年8月18日(星期五)起,我们不再使用 Google Analytics。因此,我们现在使用的所有 cookies 仅用于此网站的运营。即使是首次访问的用户,烦人的 cookie 同意弹窗现在也已关闭。

自2023年6月7日(星期五)起,由于 Optiver 的慷慨捐赠,全世界的任何人都可以自行创建一个 VisuAlgo 账户,以存储一些自定义设置(例如,布局模式,默认语言,播放速度等)。

此外,对于 NUS 学生,通过使用 VisuAlgo 账户(一个 NUS 官方电子邮件地址,课堂名册中的学生姓名,以及在服务器端加密的密码 - 不存储其他个人数据),您同意您的课程讲师跟踪您的电子讲义阅读和在线测验培训进度,这是顺利进行课程所必需的。您的 VisuAlgo 账户也将用于参加 NUS 官方的 VisuAlgo 在线测验,因此,将您的账户凭据传递给他人代您进行在线测验构成学术违规。课程结束后,您的用户账户将被清除,除非您选择保留您的账户(OPT-IN)。访问完整的 VisuAlgo 数据库(包含加密密码)的权限仅限于 Halim 教授本人。

对于全球其他已经给 Steven 写过信的 CS 讲师,需要一个 VisuAlgo 账户(您的(非 NUS)电子邮件地址,您可以使用任何显示名称,以及加密密码)来区分您的在线凭据与世界其他地方。您的账户将具有 CS 讲师特定的功能,即能够查看隐藏的幻灯片,这些幻灯片包含了在隐藏幻灯片之前的幻灯片中提出的问题的(有趣的)答案。您还可以访问 VisuAlgo 在线测验的 Hard 设置。您可以自由地使用这些材料来增强您的数据结构和算法课程。请注意,未来可能会有其他 CS 讲师特定的功能。

对于任何拥有 VisuAlgo 账户的人,如果您希望不再与 VisuAlgo 工具有关联,您可以自行删除您的账户。