Sorting problem has a variety of interesting algorithmic solutions that embody many Computer Science ideas:

1. Comparison versus non-comparison based strategies,
2. Iterative versus Recursive implementation,
3. Divide-and-Conquer paradigm (e.g., Merge Sort or Quick Sort),
4. Best/Worst/Average-case Time Complexity analysis,
5. Randomized Algorithms, etc.

1. 在数组 A 中搜索特定值 v，
   
2. 查找（静态）数组 A 中的最小/最大/第 k 个最小/最大值，
   
3. 测试唯一性并删除数组 A 中的重复项，
   
4. 计算特定值 v 在数组 A 中出现多少次，
   
5. 设置数组 A 和另一个排序数组 B 之间的交集/联合，
6. 寻找一个目标对 x∈A 和 y∈A，使得 x + y 等于目标 z 等。
7. 计算在区间 [lo..hi] 内共计有多少个值。
   

1. 完全随机的
2. 随机但有序的（按升序/降序排列）
3. 随机但几乎有序的（按升序/降序排列）
4. 随机但包含许多重复项（因此在小范围的整数内）
   
5. 完全由你自己定义。
   

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

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

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

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

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

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

我们计算操作数（算术，赋值，比较等等）而不是计算实际的时间。因为算法的运行时长与其所需的操作数紧密相关，所以这样能评估其效率。

可查看 SpeedTest.cpp | py | java 和评论（尤其注意如何获得计数器的值）。

知道一个算法所需的（准确）操作数之后，我们就可以说类似于“算法 X 解决大小为 n 的问题需要 2n² + 100n 次操作”的话了。

如果已知一个操作需要时间 t，那就可以说 X 需要 (2n² + 100n)t 个时间单位来解决大小为 n 的问题。

然而时间 t 决定于之前提到的因素，例如语言，编译器，电脑...

因此，与其拘泥于实际时间 t，我们不妨说算法 X 用了正比于 2n² + 100n 的时间来解决大小为 n 的问题。

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

1. 比较一对相邻元素（a，b），
2. 如果两项的大小关系不正确，交换这两个数（在本例中为a > b），
3. 重复步骤1和2，直到我们到达数组的末尾（最后一对是第 N-2 和 N-1 项，因为我们的数组从零开始）
4. 到目前为止，最大项将在最后的位置。 然后我们将 N 减少1，并重复步骤1，直到 N = 1。
   

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次迭代。 但内部循环运行变得越来越短：

1. 当 i = 0，内循环进行N-1次比较和交换的迭代；
   
2. 当 i = 1，N-2次迭代；
   
3. 当 i = N-2 时，1次迭代；
   
4. 当 i = N-1 时，0次迭代。

1. 在 [L ... N-1] 范围内找出最小项目 X 的位置，
   
2. 用第 L 项交换第 X 项，
   
3. 将下限 L 增加1并重复步骤1直到 L = N-2。
   

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(N²) — 实际上，这和冒泡排序很像。

插入排序类似于大多数人安排扑克牌的方式。

1. 从你手中的一张牌开始，
   
2. 选择下一张牌并将其插入到正确的排序顺序中，
   
3. 对所有牌重复上一步。
   

让我们在小的实力数组 [40,13,20,8] 上尝试 Insertion Sort。

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; // 此处为插入点
  }
}

1. 在最好的情况下，数组已经排序并且 (a [j]> X) 总是为假。所以不需要移位数据，并且内部循环在O（1）时间内运行，
   
2. 在最坏的情况下，数组被反向排序并且 (a [j]> X) 总是为真。插入始终发生在数组的前端，并且内部循环在O（N）时间内运行。
   

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

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

1. 归并排序，
   
2. 快速排序和它的随机版本（只有一个变化）。
   

1. 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组，
   
2. 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程......，
   
3. 最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组。

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] 上尝试 Merge Sort。注意其前半部分已经排序 [1, 5, 19, 20]，其下半部分也已经排序[2, 11, 15, 17]，我们只需关注合并排序算法的最后一次合并。

1. 划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
   
2. 解决步骤：结合较小的子问题的结果来解决较大的原始问题。
   

归并并排序是分而治之的排序算法。
划分步骤很简单：将当前数组分成两半（如果 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（N²）排序算法增长得慢得多。
然而，归并排序有几个不太好的部分。 首先，从零开始实现并不容易（虽然我们不必这样做）。 其次，它在归并操作期间需要额外的O（N）内存，因此会占用额外内存并且不是就地的 (in-place)。顺便说一句，如果你有兴趣看看为解决这些（经典）归并排序不那么好的部分做了什么，你可以阅读这个。

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

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

划分步骤：选择一个项目 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 的项目。 然后，递归地对这两部分进行排序。
解决步骤：不要惊讶......我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的划分步骤和解决步骤与归并排序完全相反。

1. S1 = a [i + 1..m]，其中项目 ≤ p，
   
2. S2 = a [m + 1..k-1]，其中项目 ≥ p，且
   
3. 未知的= a [k..j]，其中项目尚未分配给 S1 或 S2。
   

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(log N)。
由于每个级别进行 O(N) 比较，时间复杂度为 O(N log N)。
在这个手工制作的示例输入数组 [4, 1, 3, 2, 6, 5, 7] 上尝试Quick Sort。这在实践中很少见，因此我们需要设计一个更好的方法：随机快速排序。

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

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

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

我们都知道，所有基于比较的排序算法都具有Ω（N log N）的下限时间复杂度。要证明这个定理大概又要花一个小时的课，在这里就不证明了。
因此，任何具有最坏情况复杂度O（N log N）的基于比较的排序算法（如归并排序）都被认为是最优算法，即我们不能做得比这更好。
然而，如果存在输入数组的某些假设，我们可以避免比较这些项目来确定排序顺序， 然后使排序算法达到更快的时间复杂度 — 比如O(N)。

假设：如果要排序的项是大范围但小数位的整数，我们可以将计数排序（Counting Sort）思想与基数排序（Radix Sort）结合起来，以实现线性时间复杂度。
在基数排序中，我们将每个项排序为一个 w 位的数字串（如果需要，我们对不足 w 位的整数填充小于的前几个零）。
从最低有效位（最右边）到最高有效位（最左边），我们遍历 N 个项并将它们按照当前位放到10个队列中（每个数字[0..9]各一次），就好像 一个修改了的，保留了稳定性的计数排序。 然后我们将每个队列中的项重新连接，以进行后续迭代。
若需要更直观的解释，试试 Radix Sort。
请注意，我们只执行O(w × (N + k)) 次迭代。 在这个例子中，w = 4，k = 10。

如果排序算法在排序过程中仅需要恒定量（如 O(1)）的额外空间，则称其为就地 (in-place) 排序算法。就是这样，常数的少量额外变量是可以的，但我们不允许具有取决于输入数组长度 N 的可变长度的变量。
归并排序（经典版），由于其合并子程序需要额外的大小为 N 的临时数组，因此不是就地的。
讨论：冒泡排序，选择排序，插入排序，快速排序（是否随机），计数排序和基数排序如何？哪些是就地的？

我们已经到了电子讲座 - 排序的末尾。
但是，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) 数据结构等。