Sorting problem has a variety of interesting algorithmic solutions that embody many Computer Science ideas:
第二个操作是最重要的操作：通过单击“Sort”按钮来执行排序算法。
需要注意的是，你可以通过切换页面顶部的算法缩写来切换当前算法。
为了节省屏幕空间，我们将算法名称缩写为三个字符:
在接下来的幻灯片，我们将讨论三种基于比较的排序算法
你应该已经了解下列知识：
-. 对数和指数, 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 和评论（尤其注意如何获得计数器的值）。
知道一个算法所需的（准确）操作数之后，我们就可以说类似于“算法 X 解决大小为 n 的问题需要 2n2 + 100n 次操作”的话了。
如果已知一个操作需要时间 t，那就可以说 X 需要 (2n2 + 100n)t 个时间单位来解决大小为 n 的问题。
然而时间 t 决定于之前提到的因素，例如语言，编译器，电脑...
因此，与其拘泥于实际时间 t，我们不妨说算法 X 用了正比于 2n2 + 100n 的时间来解决大小为 n 的问题。
写作算法 A 有时间复杂度 O(f(n))，其中 f(n) 是算法 A 的增长率函数。
void bubbleSort(int a[], int N) { // 标准版本
for (; N > 0; --N) // N次迭代
for (int i = 0; i < N-1; ++i) // 除最后一次, O(N)
if (a[i] > a[i+1]) // 若数组元素i和i+1成非递减次序
swap(a[i], a[i+1]); // 在O(1)时间内交换
}比较和交换需要一个以常量为界的时间，我们称之为c。
（标准）冒泡排序中有两个嵌套循环。
外循环正好运行N次迭代。 但内部循环运行变得越来越短：
void selectionSort(int a[], int N) {
for (int L = 0; L <= N-2; L++) { // O(N)
找到[L,N-1]区间的最小的数的序号X // O(N)
swap(X, L) // O(1), 注意X可能等于L（没有交换）
}
}复杂度: O(N2) — 实际上，这和冒泡排序很像。
Quiz: How many (real) swaps are required to sort [29, 10, 14, 37, 13] by Selection Sort?
插入排序类似于大多数人安排扑克牌的方式。
让我们在小的实力数组 [40,13,20,8] 上尝试 。
void insertionSort(int a[], int N) { //插入排序
for (int i = 1; i < N; i++) { // O(N)
X = a[i]; // X 是要被插入的那个数
for (j = i-1; j >= 0 && a[j] > X; j--) // 速度有快有慢
a[j+1] = a[j]; // 为 X 腾出一个空间
a[j+1] = X; // 此处为插入点
}
}
Quiz: What is the complexity of Insertion Sort on any input array?
我们将在接下来的几张幻灯片中讨论两种基于比较的排序算法：
void merge(int a[], int low, int mid, int high) {
// subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
int N = high-low+1;
int b[N]; // 讨论: 为什么我们需要一个临时的数组 b?
int left = low, right = mid+1, bIdx = 0;
while (left <= mid && right <= high) // 归并
b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
while (left <= mid) b[bIdx++] = a[left++]; // leftover, if any
while (right <= high) b[bIdx++] = a[right++]; // leftover, if any
for (int k = 0; k < N; k++) a[low+k] = b[k]; // copy back
}
在示例数组 [1, 5, 19, 20, 2, 11, 15, 17] 上尝试 。注意其前半部分已经排序 [1, 5, 19, 20]，其下半部分也已经排序[2, 11, 15, 17]，我们只需关注合并排序算法的最后一次合并。
归并并排序是分而治之的排序算法。
划分步骤很简单：将当前数组分成两半（如果 N 是偶数，则将其完全平等，或者如果 N 是奇数，则一边多一项），然后递归地对这两半进行排序。
解决步骤是主要的工作：使用前面讨论的归并子程序合并两个（排序的）半部分以形成一个有序数组。
void mergeSort(int a[], int low, int 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); // 解决步骤: 归并子程序
}
}
无论输入的原始顺序如何，归并排序中最重要的部分是其O（N log N）性能保证。 就这样，没有任何针对性的测试用例可以使归并排序对于N个元素数组运行比O（N log N）更长的时间。
因此，归并排序非常适合大数组的排序，因为O（N log N）比前面讨论的O（N2）排序算法增长得慢得多。
然而，归并排序有几个不太好的部分。 首先，从零开始实现并不容易（虽然我们不必这样做）。 其次，它在归并操作期间需要额外的O（N）内存，因此会占用额外内存并且不是就地的 (in-place)。顺便说一句，如果你有兴趣看看为解决这些（经典）归并排序不那么好的部分做了什么，你可以阅读这个。
归并排序也是一个稳定 (stable) 的排序算法。 讨论：为什么？
快速排序是另一个分而治之的排序算法（另一个在这个可视化页面中讨论的是归并排序）。
在继续随机化和可用版本的快速排序之前，我们将看到，这种确定性的，非随机化的快速排序的版本可能在针对性输入中具有很差的 O(N2) 时间复杂度。
划分步骤：选择一个项目 p（称为pivot）然后将项目 a[i..j] 分为三部分：a [i..m-1]，a [m] 和 a[m + 1..j]。 a [i..m-1]（可能为空）包含小于等于 p 的项目。 a [m] 是pivot p，例如：索引 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1..j]（可能为空）包含大于等于 p 的项目。 然后，递归地对这两部分进行排序。
解决步骤：不要惊讶......我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的划分步骤和解决步骤与归并排序完全相反。
![Case when a[k] ≥ p, increment k, extend S2 by 1 item](https://visualgo.net/img/partition1.png)
![Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item](https://visualgo.net/img/partition2.png)
int partition(int a[], int i, int j) {
int p = a[i]; // p 是 pivot
int m = i; // S1 和 S2 一开始是空的
for (int k = i+1; k <= j; k++) { // 探索未知的区域
if (a[k] < p) { // case 2
m++;
swap(a[k], a[m]); // C++ STL algorithm std::swap
} // 注意：在情况1的时候我们什么都不做: a[k] >= p
}
swap(a[i], a[m]); // 最后一步, 用a[m]交换 pivot
return m; // 返回pivot的索引, 用于快速排序（Quick Sort）
}
void quickSort(int a[], int low, int 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); // 然后将右侧子数列排序
}
}
首先，我们分析一次分区的成本。
在函数 partition(a, i, j) 中，只有一个遍历了 j-i 次的 for 循环。 由于 j 可以和 N-1 一样大，i 可以低至0，所以分区的时间复杂度是O(N)。
类似于归并排序分析，快速排序的时间复杂度取决于 partition(a, i, j) 被调用的次数。
在这种最坏情况的输入场景中，会发生以下情况：
第一次分区需要 O(N) 时间，将 a 分成 0, 1, N-1个项，然后向右递归。当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。
当发生这种情况时，递归的深度只有 O(log N)。
由于每个级别进行 O(N) 比较，时间复杂度为 O(N log N)。
在这个手工制作的示例输入数组 [4, 1, 3, 2, 6, 5, 7] 上尝试。这在实践中很少见，因此我们需要设计一个更好的方法：随机快速排序。
在接下来的幻灯片，我们将讨论两种不基于比较的排序算法:
这些排序算法可以不比较数组的项，从而比时间复杂度为 Ω（N log N）的基于比较的排序算法的下限更快。
It is known (also not proven in this visualization as it will take about half-an-hour lecture about decision tree model to do so) that all comparison-based sorting algorithms have a lower bound time complexity of Ω(N log N).
Thus, any comparison-based sorting algorithm with worst-case complexity O(N log N), like Merge Sort is considered an optimal algorithm, i.e., we cannot do better than that.
However, we can achieve faster sorting algorithm — i.e., in O(N) — if certain assumptions of the input array exist and thus we can avoid comparing the items to determine the sorted order.
Assumption: If the items to be sorted are Integers with small range, we can count the frequency of occurrence of each Integer (in that small range) and then loop through that small range to output the items in sorted order.
Try on the example array above where all Integers are within [1..9], thus we just need to count how many times Integer 1 appears, Integer 2 appears, ..., Integer 9 appears, and then loop through 1 to 9 to print out x copies of Integer y if frequency[y] = x.
The time complexity is O(N) to count the frequencies and O(N+k) to print out the output in sorted order where k is the range of the input Integers, which is 9-1+1 = 9 in this example. The time complexity of Counting Sort is thus O(N+k), which is O(N) if k is small.
We will not be able to do the counting part of Counting Sort when k is relatively big due to memory limitation, as we need to store frequencies of those k integers.
PS: This version of Counting Sort is not stable, as it does not actually remember the (input) ordering of duplicate integers. The version presented in CLRS is stable, but is a bit more complex than this form.
Assumption: If the items to be sorted are Integers with large range but of few digits, we can combine Counting Sort idea with Radix Sort to achieve the linear time complexity.
In Radix Sort, we treat each item to be sorted as a string of w digits (we pad Integers that have less than w digits with leading zeroes if necessary).
For the least significant (rightmost) digit to the most significant digit (leftmost), we pass through the N items and put them according to the active digit into 10 Queues (one for each digit [0..9]), which is like a modified Counting Sort as this one preserves stability (remember, the Counting Sort version shown in this slide earlier is not a stable sort). Then we re-concatenate the groups again for subsequent iteration.
Try on the random 4-digits array above for clearer explanation.
Notice that we only perform O(w × (N+k)) iterations. In this example, w = 4 and k = 10.
Now, having discussed about Radix Sort, should we use it for every sorting situation?
For example, it should be theoretically faster to sort many (N is very large) 32-bit signed integers as w ≤ 10 digits and k = 10 if we interpret those 32-bit signed integers in Decimal. O(10 × (N+10)) = O(N).
Discussion: Using base-10 as shown in this visualization is actually not the best way to sort N 32-bit signed integers. What should be the better setup?
如果排序算法在排序过程中仅需要恒定量（如 O(1)）的额外空间，则称其为就地 (in-place) 排序算法。就是这样，常数的少量额外变量是可以的，但我们不允许具有取决于输入数组长度 N 的可变长度的变量。
归并排序（经典版），由于其合并子程序需要额外的大小为 N 的临时数组，因此不是就地的。
讨论：冒泡排序，选择排序，插入排序，快速排序（是否随机），计数排序和基数排序如何？哪些是就地的？
A sorting algorithm is called stable if the relative order of elements with the same key value is preserved by the algorithm after sorting is performed.
Example application of stable sort: Assume that we have student names that have been sorted in alphabetical order. Now, if this list is sorted again by tutorial group number (recall that one tutorial group usually has many students), a stable sort algorithm would ensure that all students in the same tutorial group still appear in alphabetical order of their names. Radix sort that goes through multiple round of sorts digit-by-digit requires a stable sort sub-routine for it to work correctly.
Discussion: Which of the sorting algorithms discussed in this e-Lecture are stable?
Try sorting array A = {3, 4a, 2, 4b, 1}, i.e. there are two copies of 4 (4a first, then 4b).
Quiz: Which of these algorithms run in O(N log N) on any input array of size N?
Quiz: Which of these algorithms has worst case time complexity of Θ(N^2) for sorting N integers?
Bubble Sort我们已经到了电子讲座 - 排序的末尾。
但是，VisuAlgo 中还有另外两种嵌入在其他数据结构中的排序算法：堆排序和平衡BST排序。 我们将在这两种数据结构的电子讲座里面讨论它们。
实际上，许多这些基本排序算法的C ++源代码已经分散在这些电子讲座幻灯片中。对于其他编程语言，您可以将给定的C ++源代码翻译为其他编程语言。
通常，排序只是问题解决过程中的一小部分，而现在大多数编程语言都有自己的排序函数，所以非必要情况，我们不需要复现其代码。
在C++中，您可以使用STL算法中的std::sort，std::stable_sort 或 std::partial_sort。
在Java中，您可以使用Collections.sort。
在Python中，您可以使用sort。
在OCaml中，您可以使用List.sort compare list_name。
如果比较函数是针对特定问题的，我们可能需要为这些内置的排序例程提供额外的比较函数。
现在您已经到了电子讲座的最后部分，您认为排序问题与调用内置的排序程序一样简单吗？
尝试这些在线评判问题以了解更多信息：
Kattis - mjehuric
Kattis - sortofsorting，或者
Kattis - sidewayssorting
这不是排序算法的结束。 当您在 VisuAlgo 中探索其他主题时，您会意识到排序是许多其他高难度问题的高级算法的预处理步骤，例如， 作为克鲁斯卡尔算法（Kruskal's algorithm）的预处理步骤，创造性地用于后缀数组 (Suffix Array) 数据结构等。