引言：
  在排序的最终结果中，各元素的次序依赖于它们之间的比较，我们把这类排序算法称为比较排序，对于包含n个元素的输入序列来说，任何比较排序在最坏情况下都要经过 $\Omega (nlgn)$次比较，下面将讨论三种线性时间复杂度的排序算法。

1.排序算法的下界

  比较排序可以被抽象为一棵决策树，以下是作用于三个元素时的比较排序决策树：

  在决策树中，，每个内部节点都以 $i:j$ 标记，其中，i 和 j 满足 $1\le i,j\le n$，n 是输入序列中的元素个数，每个叶节点上都标注一个序列 $<\pi (1)，\pi (2)，...,\pi (n)>$，排序算法的执行对应于一条从树的根节点到叶结点的路径。每一个内部节点表示一次比较 $a_i\le a_j$。左子树表示一旦我们确定 $a_i\le a_j$之后的后续比较，右子树表示在确定了$a_i>a_j$的后续比较。当到达叶节点时，表示排序算法已经确定了一个顺序$a_{\pi (1)}\le a_{\pi (2)}\le ...\le a_{\pi (n)}$。
  在决策树中，从根节点到任意可达叶节点之间的最长简单路径的长度，表示的是对应排序算法中最坏情况下的比较次数。因此，一个比较排序算法中最坏情况比较次数就等于决策树的高度。
  对于正确的比较排序算法来说，n 个元素的 n！种可能的排列都应该出现在决策树的叶结点上。在一棵高为 h 、具有 l 个可达叶结点的决策树中，输入数据的 n！中可能的排列都是叶节点，所以有 $n!\le l$ 。由于二叉树的高为h，叶结点的数目不多于 $2^h$，我们可以得到：$$n!\le l\le 2^h$$对该式两边取对数有$$\begin{array}{rl}h& \ge lg(n!)\\ & =\Omega (nlgn)\end{array}$$ 由此，我们可以得到比较排序算法中的最坏情况比较时间复杂度至少为 $nlgn$

2.计数排序

计数排序的要求： n个输入元素中的每一个都是在 0 到 k 之间的整数，其中 k 为某个整数。

计数排序的基本思路： 对于每一个输入的元素x，确定小于 x 的元素的个数。利用这一信息，我们可以直接把 x 放到它在输出数组中的位置上。

计数排序算法可视化：

1. 统计数组A中 0 到 k 元素出现的个数，A数组中元素 i 的个数存放在 C 数组下标 i 的位置。
   
2. 对数组 C 进行前缀和处理。
   
3. 将数组A中的值倒序遍历按照其在映射到 C 数组中对应的下标位置idx，找到其元素值 val ，存放在 B 数组的相应位置，存放完成后，将 val 的值减一。
   
4. 重复过程三，遍历数组 A ，完成排序。

计数排序伪代码：
  假设输入是一个数组 A[ 1…n ]，A.length = n，B[ 1…n ]数组存放排序的输出，C[ 1…n ]提供临时存储空间。

	COUNT—SORT(A,B,k)// 初始化备用数组，将其 0 到 k 之间的下标元素都置为 0let i = 0 to kC[i] = 0// 统计元素值为 A[j] 的元素个数，A[j]作为下标，C[A[j]]作为A[j]的个数for j = 1 to A.lengthC[A[j]] = C[A[j]] + 1// 从 1 到 k 进行前缀和处理，统计比i小的元素有几个for i = 1 to kC[i] = C[i] + C[i-1]// 将A数组从后向前遍历（保证其稳定），是每一个元素插入相应的位置。for j = A.length downto 1B[C[A[j]]] = A[j]C[A[j] = C[A[j] - 1

C++实现计数排序：

• 头文件：

#include <iostream>  
#include <vector>  
#include <algorithm> 

• 调用与传参：

vector<int> A = { 4, 2, 2, 8, 3, 3, 1, 12, 56, 47 };
auto max_num_iter = max_element(A.begin(), A.end());
Counting_Sort(A,*max_num_iter);

• 函数：

void Counting_Sort(vector<int>& A, int max_value) {// 创建计数数组，用于存储每个数字出现的次数  vector<int> C(max_value + 1, 0);// 统计每个数字出现的次数  for (int i = 0; i < A.size(); i++) {C[A[i]]++;}// 求前缀和for (int i = 1; i <= max_value; i++) {C[i] += C[i - 1];}// 创建临时数组，用于存储排序后的数字序列  vector<int> B(A.size());// 从后向前遍历原始数组，将数字按照计数数组中的顺序放入临时数组中  for (int i = A.size() - 1; i >= 0; i--) {B[--C[A[i]]] = A[i];}// 将临时数组中的数字复制回原始数组  for (int i = 0; i < A.size(); i++) {A[i] = B[i];}
}

计数排序时间复杂度分析： 第一个循环所花的时间为 $\theta (k)$，第二个循环所花的时间为 $\theta (n)$，第三个循环所花的时间为 $\theta (k)$，第四个循环所花的时间为 $\theta (n)$，所以，总的时间代价为 $\theta (k+n)$，在实际工作中（例如对高考成绩排序），当 $k=O(n)$ 时，我们会采用计数排序，这样运行时间为 $O(n)$。

3.基数排序

基数排序的要求： 只能针对整数进行排序。

基数排序的基本思路： 针对输入数组元素中的每一个数，按照从低位（个位）到高位的方法，利用稳定的排序算法进行排序。

基数排序算法可视化：

基数排序伪代码：

RADIX-SORT(A,d)for i = 1 to duse a stable sort to sort array A on digit i

C++实现基数排序：

• 头文件：

#include <iostream>  
#include <vector>  

• 调用与传参：

vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66};
Radix_Sort(arr);

• 函数：

 void Radix_Sort(vector<int>& arr) {// 找到数组中的最大值  int max_num = arr[0];for (int i = 1; i < arr.size(); i++) {if (arr[i] > max_num) {max_num = arr[i];}}// 从最低位开始，按照每个数字的位数进行排序  int exp = 1; // 当前位数  while (max_num / exp > 0) {// 创建桶数组，用于存储当前位数的数字计数  vector<int> bucket(10, 0);for (int i = 0; i < arr.size(); i++) {// 将当前数字放入对应的桶中  bucket[(arr[i] / exp) % 10]++;}// 将桶中的计数转换为累计计数，方便后续放入数字  for (int i = 1; i < 10; i++) {bucket[i] += bucket[i - 1];}// 创建临时数组，用于存储排序后的数字序列  vector<int> temp(arr.size());// 从后向前遍历原始数组，将数字按照当前位数放入对应的桶中  for (int i = arr.size() - 1; i >= 0; i--) {temp[--bucket[(arr[i] / exp) % 10]] = arr[i];}// 将临时数组中的数字复制回原始数组  for (int i = 0; i < arr.size(); i++) {arr[i] = temp[i];}// 更新当前位数  exp *= 10;}
}

基数排序时间复杂度分析：

• 引理1：给定 n 个 d 位数，其中每一个数位有 k 个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时 $\theta (n+k)$，那么它就可以在 $\theta (d\ast (n+k))$ 时间内将这些数排好序。
• 引理2：给定 n 个 b 位二进制数和任何整数 $r\le b$，如果RADIX-SORT使用的稳定排序算法对数据取值区间是 0 到 k 的输入进行排序耗时 $\theta (n+k)$，那么它就可以在 $\theta ((b/r)(n+2^r))$时间内将这些数据排好序。

4.桶排序

桶排序的要求： 输入数据服从均匀分布，元素取值在 [0,1) 之间。

桶排序的基本思路： 桶排序将 [0,1) 区间划分为 n 个相同大小的子区间，或称为桶。然后，将 n 个输入数分别放到各个桶中。因为输入数据是均匀、独立分布在 [0,1) 区间上，所以一般不会出现很多数落在一个区间的情况。为了得到输出结果，我们先对每个桶中的数进行排序，然后遍历每一个桶，按照次序把各个桶中的元素列出来即可。

桶排序算法可视化：

桶排序伪代码：

BUCKET-SORT(A)n = A.lengthlet B[0..n-1] be a new arrayfor i =0 to n-1make B[i] an empty listfor i = 1 to ninsert A[i] into list B[floor(nA[i])]for i = 0 to n-1sort list B[i] with insertion sortconcatenate the list B[0],B[1],...,B[n-1] together in order

C++实现桶排序：

• 头文件：

# include <vector>  
# include <iostream>
# include <algorithm>  
# include <cmath>

• 调用与传参：

vector<float> A = { 0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68 };
Bucket_Sort(A);

• 函数：

void Bucket_Sort(vector<float>& A) {int n = A.size();// Step 1: 初始化桶数组 B  vector<vector<float>> B(n);// Step 2: 将元素插入到对应的桶中  for (int i = 0; i < n; i++) {int bucketIndex = n * A[i]; // 计算元素应进入哪个桶  B[bucketIndex].push_back(A[i]);}// Step 3: 对每个桶中的元素进行排序，这里使用插入排序  for (int i = 0; i < n; i++) {sort(B[i].begin(), B[i].end());}// Step 4: 将排序后的桶合并到一起  int index = 0; // 用于跟踪合并后的数组中的下一个空位置  for (int i = 0; i < n; i++) {for (int j = 0; j < B[i].size(); j++) {A[index++] = B[i][j];}}
}

桶排序时间复杂度分析：
  假设 $n_i$ 表示桶 B[i] 中元素个数的随机变量，因为插入排序的的时间是平方阶的，索引桶排序的时间代价为：$$T(n)=\theta (n)+\sum _{i=1}^{n-1}O(n_i^2)$$

  对上式两边取期望，并利用期望的线性性质得到：$$\begin{array}{rl}E[T(n)]& =E[\theta (n)+\sum _{i=1}^{n-1}O(n_i^2)]\\ & =\theta (n)+\sum _{i=1}^{n-1}E[O(n_i^2)]\\ & =\theta (n)+\sum _{i=1}^{n-1}OE[(n_i^2)]\end{array}$$

  因为输入数组 A 的每一个元素是等概率的落入任意一个桶中，所以每个桶 i 具有相同的期望值 $E[n_i^2]$，我们定义随机变量：对所有 i = 0，1，…，n-1 和 j = 1，2，…，n， X i j = I { A [ j ] 落入桶 i } X_{ij}=I \{ A[j]落入桶 i \} Xij​=I{A[j]落入桶i}

  因此有：$$n_i=\sum _{j=1}^n{X}_{ij}$$

  为了计算 $E[n_i^2]$ ，我们展开平方项，并重新组合各项：
$$\begin{array}{rl}E[n_i^2]& =E[(\sum _{j=1}^n{X}_{ij}{)}^2]\\ & =E[\sum _{j=1}^n\sum _{k=1}^n{X}_{ij}{X}_{ik}]\\ & =E[\sum _{j=1}^n{X}_{ij}^2+\sum _{j=1}^n\sum _{k=1,k\ne j}^n{X}_{ij}{X}_{ik}]\\ & =\sum _{j=1}^{n}E[X_{ij}^2]+\sum _{j=1}^n\sum _{k=1,k\ne j}^{n}E[X_{ij}{X}_{ik}]\end{array}$$

  接下来我们计算最后的两项，$X_{ij}$ 为 1 的概率为$\frac{1}{n}$ ，其他情况都是 0，于是有：$$E[X_{ij}^2]=1^2\ast \frac{1}{n}+0^2\ast (1-\frac{1}{n})=\frac{1}{n}$$

  当 $k\ne j$时，随机变量$X_{ij}和X_{ik}$是独立的，因此有：
$$E[X_{ij}{X}_{ik}]=E[X_{ij}]E[X_{ik}]=\frac{1}{n}\ast \frac{1}{n}=\frac{1}{n^2}$$

  将这两个期望值代入公式得到：
$$\begin{array}{rl}E[n_i^2]& =\sum _{j=1}^n\frac{1}{n}+\sum _{j=1}^n\sum _{k=1,k\ne j}^n\frac{1}{n^2}\\ & =n\ast \frac{1}{n}+n(n-1)\ast \frac{1}{n^2}\\ & =1+\frac{n-1}{n}\\ & =2-\frac{1}{n}\end{array}$$

  最终我们可以得到结论，桶排序的期望运行时间为：$$\theta (n)+n\ast O(2-1/n)=\theta (n)$$
  即使输入数据不服从均匀分布，只要输入的数据满足：所有的桶的大小的平方和与总的元素的个数呈线性关系，那么桶排序仍能在线性时间内完成。