线性时间排序

【比较排序】

• 排序结果中，各元素的次序基于输入元素间的比较——这类排序算法称为比较排序。
• 归并排序，堆排序，快排都属于比较排序

【上界O(nlogn)】

• 归并排序和堆排序在最坏情况下达到线性对数的时间上界
  p.s. 第一部分可证得归并排序和堆排序是渐进最优的
  
• 快速排序在平均情况下达到线性对数的时间上界

一. 排序（比较）算法时间的下界

【本节索引】

• 对于含有n个元素的一个输入序列，任何比较排序算法在最坏情况下都要用Ω(nlogn)次比较进行排序。
• 对于诸如基数排序、计数排序、桶排序这样的费比较算法，时间下界Ω(nlogn)对它们并不适用。

1. 决策树模型

（1）比较排序

①特性：在比较排序算法中，仅用比较来确定输入序列<a₁，a₂，…，a_n>的元素间次序。即：对于给定的两个元素a_i和a_j，通过测试a_i<a_j，a_i≤a_j，a_i=a_j，a_i≥a_j或a_i>a_j中的哪一个关系成立以确定a_i和a_j之间的相对次序。

②假设所有的比较都是a_i≤a_j的形式

假设所有输入元素都是不同的，那么“=”关系的判定就失去意义，且“≤”和“<”（>亦同）之间的比较是等价的。

又“≤”和“≥”二者进行判定所包含的信息量一致，基于此，我们选定采用“≤”进行元素之间的比较。

（2）决策树的一般结构

一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较。

p.s. 但是下方的决策树模型并不能很好地适用于归并排序和快排，因为下方的决策树的绘制是依赖于特定的n值——也就是说排序的问题规模是确定的。

①节点

【内节点】
每个内节点上都注明有i：j，表示对下标为i和j的两个元素进行比较。
其中——1≤i,j≤n，i,j表示输入序列中元素的下标

【叶节点】
每个叶节点都注明排列<π(1),π(2),…,π(n)>；表示排序一种结果。

②路径

排序算法的执行对应于遍历一条从树的根节点到叶节点的路径。

• 排序过程中，在每个内节点都会做一次元素比较a_i≤a_j
• 内节点的左子树决定着a_i≤a_j以后的比较，而右子树决定着a_i>a_j以后的比较
• 到达叶节点后，排序算法就确定了最终的顺序

③排序算法正确工作的必要条件

【排序的每一种排列都会作为决策树上可达的叶子出现】

也就是说，n个元素的n!中排列中的每一种都要作为决策树的一个叶子而出现。因为任何正确的排序算法都必须能够产生其输入的每一种排列，对根节点来说，每一个叶子都必须是可以经由某条路径达到的。

（3）对3个元素进行插入排序的决策树结构

Tip1：含有n个元素的某一排序方法对应的决策树结构是稳定的，就像是一个算法模板一样。当输入序列发生变化时，只是算法运行过程中选择的路径不同，但整个决策树并不会发生变化。

Tip2：基于第一点，读者应该可以更加深刻地理解“决策树是一棵满二叉树”，“排序有多少种可能的结果就会有多少个决策树的叶子节点”这些结构特点。

2. 最坏情况下界

（1）排序的比较次数↔决策树的高度

①在决策树中，从根到任意一个可达叶节点之间最长路径的长度（最长路径的长度也就是该叶节点所在的树高），表示对应的排序算法中最坏情况下的比较次数。

②如果决策树中每种排列都以可达叶子的形式出现，那么关于其决策树高度的下界↔比较排序算法运行时间的下界。

（2）定理：任意一个比较排序算法在最坏情况下，都需要做Ω(nlogn)次的比较。

p.s. 此处详细的数学证明可以参考下方截图，其涉及的主要是渐进符号以及上下界的相关知识，感兴趣的读者可以自行深入了解。

也就是说当不等式转换成h≥lg(n!)之后，我们问题的关键就变成了求解lg(n!)的下界，用斯特林公式正好可以得到阶乘运算的近似解。

（3）推论：堆排序和归并排序都是渐进最优的比较排序算法

堆排序和归并排序的运行时间上界为O(nlogn)，和上述定理给出的最坏情况下界是一致的。

说到渐进，因为这些算法是依赖于n的，并且忽略了常数因子，这些算法随着n的递增趋于最优。

二. 计数排序

1. 计数排序算法的思想

（1）数据要求：假设n个输入元素中的每一个都是介于0到k之间的整数，k为某个整数。

（2）基本思想：对每一个输入元素x，确定出小于x的元素个数。明确了这一信息之后，就可以把x直接放到它在最终输出数组中的位置上。

比如说有17个元素小于x，那么就可以知道x属于第18个输出位置。

p.s. 当有几个元素相同时，上述方案就要略作修改。（后面的代码中会体现到，比如从最后开始放元素，每次放完之后计数数组的值都要自减…）

2. 代码实现

• 数据输入：数组A[1…n]，length[A] = n；提供等待排序的输入数据
• 数据输出：数组B[1…n],存放排序的最终结果
• 辅助空间：数组C[0…k]，存储每一个整数k在输入数据中出现的次数（输入数据中每一个≤k的元素个数）

#include<bits/stdc++.h>
using namespace std;

vector<int> CountingSort(vector<int> A,int k){
    //A是输入数据，且每个元素不大于k
	vector<int> C(k+1,0);//初始化计数数组
	vector<int> B(A.size());//初始化结果数组 
	for(int i = 1;i<A.size();i++)
	    C[A[i]]++; 	
	for(int i = 1;i<C.size();i++)
	     C[i] += C[i-1];
    for(int i = A.size()-1;i>0;i--){
    //从最后一个元素开始放置，考虑到相同元素和排序的稳定性
    	B[C[A[i]]] = A[i];
    	C[A[i]]--;//计数值自减，下一个相同的元素直接进入输出数组B中A[i]的前一个位置
	}
	return B;
}

//测试程序 
int main(){
	vector<int> A;
	A.push_back(-1);//占位，0位不在排序中使用 
	int tmp;
	while(cin>>tmp){
		if(tmp!='\n') 
		    A.push_back(tmp);
		else
		    break;
	}
	vector<int> B = CountingSort(A,5);
	for(int i = 1;i<B.size();i++)
	    cout<<B[i]<<" ";
	cout<<endl;
	return 0;
}
 

• 过程轨迹
  

3. 时间复杂度分析

（1）对于n个均介于0到k之间的输入元素的计数排序问题，当k = O（n）时，所运行时间为θ(n)。

因此要想让计数排序的过程正确且高效的运行，不仅需要使输入元素的每一个值都是整数，而且还需要使得其数值涵盖的范围不太大。

（2）分析

①第一组for循环（元素计数），θ(n)。
②第二组for循环（元素累计），θ(k)。
③第三组for循环（元素放置），θ(n)。

总的时间为θ(k+n)；在实践中，当k = O(n)时，我们常常采用计数排序，这时运行时间为θ(n)。

（3）特点和性质

①计数排序不是采用元素之间的比较，而是采用输入元素的实际值来确定它们在数组中的位置，因此排序算法的线性对数下界对其不适用。

②计数排序是稳定的：具有相同值的元素在输出数组中的相对次序和他们在输入数组中的次序相同。

计数排序的稳定性重要的原因之一，在于计数排序常常用作基数排序的一个子过程。

三. 基数排序

1. 实际背景

这一块的内容并不是必要的，但是个人感觉可以对基数排序算法建立一个直观的印象，从具体到抽象，方便以后碰到更加复杂的问题时能够跳出来思考是否适用于基数排序。

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每一列可以在12个位置中的任一处穿孔。排序机对这一叠卡片中的每一张的每一列进行检查（且排序机一次只能查看一个列的穿孔情况），根据穿孔的位置将它们分别放入12个盒子中（在第一个位置穿孔了就放在第一个盒子里，以此类推）。

最后操作员需要将这一堆卡片按照不同列的不同穿孔位置进行一个放置。

可以把这穿卡机排序问题中的列和穿孔位置作为两个排序的优先级因素。

因此，基数排序常常用在多位整数的排序问题中。拿d位10进制数字举例，如果一个数字对应一张卡片，那么一张卡片只需要d列，每一列对应一个数位；每一列只需要10个穿孔位置，每一个穿孔处对应10个基数单元中的每一个数字。

OS：这么描述起来，基数排序也特别像是在拨算盘。

2. 排序思想

（1）基本思想

简单来厘清一下计数排序到基数排序的一个发展历程。在前文，我们已经说过了，当k = O（n）的时候计数排序才是可行的，但是基数排序给了我们除了更大规模字的可能性。

基数排序首先按照最低有效位数字进行排序。将最低位进行排序后分成了各堆，按照0号-1号-…-n（一共有n+1个基数）号盒子的顺序(具体情况具体分析)将各堆卡片收集成一叠。

然后，对整个一叠卡片再按照次低有效位进行排序，并把结果按照同样方法再合并起来。

重复上述过程，直到对所有的d位数字都进行了排序。

只需要d遍(对于一个d位数来说)就可以将全部元素进行排序

（2）实际过程

下图所示对7个3位十进制数字进行排序的过程。

把上面抽象的排序描述过程用上例具体地展开，对于左边第一列输入数据，首先按照个位数进行排序得到第二列中间结果，再分别按照十位和百位得到第三列和第四列的数据。

两个红框和两个绿框显示的是，基数排序在每一轮的排序都是稳定的。

看一下第三列到第四列的排序过程，在按照最高位排序得到第四列之前，第三列的数字看起来还是完全乱序的。
但是如果你只看第三列的每个数字的低两位，它们是完全有序的。

由此也可以自己推敲出“从低位排序”的算法可行性，当高位的两个数字是相同的时候，后缀低位已经按照顺序排好了。

基于上述的实际过程与分析，算法的正确性能够很好地得到证明。
采用归纳假设的思想，假设低k-1位已经排序好了，现在对第k位进行排序：

• 当第k位相同时，保持原顺序→根据归纳假设可知这就是正确的顺序
• 当第k位不相同时，则当前排序算法会将其调整到正确的位序。

（3）特点与性质

①基数排序的按位排序要稳定

• 在每一位（列）上选择的排序算法必须是稳定的；所以之间我们说计数排序的稳定性对于基数排序也很重要
• 每次排序后对元素的合并（操作员将卡片从不同的盒子里拿出来合并在一起时）也不能改变卡片之间的次序

②可以采用基数排序来对有多个关键字域的记录进行排序。比如，对含有年、月、日的日期进行排序

• 通常我们会自定义结构体和比较函数（多层比较）
• 有了基数排序之后，我们可以依次按照日、月、年对数据进行三轮排序，即可得到最终结果。

3. 代码实现

#include<bits/stdc++.h>
using namespace std;

int data[10]={73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
int tmp[10];
int cc[10];
int maxbit(int data[],int n){
	int d = 1;//记录这一组数中最长的数位长度 
	for(int i = 0;i<n;i++){
		int c = 1;//记录当前这个数的长度 
		int p = data[i];
		while(p / 10){
			p /= 10;
			c++;
		}
		if(c >d)
		    d = c;
	}
	return d; 
}

void RadixSort(int data[],int n){//如果所有元素的位数统一给定，则不需要调用maxbit计算位数 
	int d = maxbit(data,n);
	int r = 1;
	while(d--){//有多少位数就要进行多少轮的排序 
	for(int i = 0;i<d;i++)
	    cc[i] = 0;//清零
	for(int i = 0;i <n;i++){
		int k = data[i] / r;
		int q= k % 10;
		cc[q]++;
	} 
	for(int i = 1;i<10;i++)
	    cc[i] += cc[i-1];//计算累加值
	for(int j = n-1;j>=0;j--){
		int p = data[j] / r;
		int s = p % 10;
		tmp[cc[s]-1] = data[j];
		cc[s]--;
	} 
	for(int i = 0;i<n;i++)
	    data[i] = tmp[i];
	r*= 10;
}
}
int main(){//测试程序 
	cout<<"排序前的数值:"<<endl;
	for(int i = 0;i<10;i++)
	    cout<<data[i]<<" ";
	cout<<endl;
	RadixSort(data,10);
	cout<<"排序后的数值:"<<endl;
	for(int i = 0;i<10;i++)
	    cout<<data[i]<<" ";
	cout<<endl;
	return 0; 
}

①代码参考《基数排序算法实现》
②从宏观来看，基数排序就是从最低位开始，针对每一位调用一次稳定排序即可。
③从微观来看，每一轮我们都采用计数排序，注意看排序函数里面最后四个for循环，是完全符合计数排序的逻辑。

只不过细节部分，我们控制了一个变量r来对每一轮某一数位上的数字进行选择；利用“/”和“%”运算将数字剥离出来。

4. 基数排序采用低位原则的原因

《基数排序为什么不能从高位开始？》
（1）最直白来说，因为如果按照我们以上逻辑（每次进行一轮排序之后，再按序混合进行下一轮排序）进行多次排序，最后得到的结果依然是乱序的。

这是受到排序项的优先级影响的，越高位的数字对于元素之间的前后关系影响会更大。

（2）换一种逻辑我们也可以按照最高位对一堆元素进行排序。先选择最高位的数字进行排序，将一堆数字分到了各个小堆中；之后我们需要递归地对每个小堆中的元素选择次高位进行排序。

既然是递归的过程，那么在过程中会产生很多临时空间来存放还未经排序的数据，效率过低。

5. 基数排序的时间复杂度

（1）给定n个d位数，每一个数位都可以取k种可能的值（某种形式的k进制）。基数排序算法能以θ(d(n+k))的时间正确地对这些数进行排序。

基数排序的时间复杂度还是要取决于选择哪一种稳定的中间排序。

通常来说，每位数字都介于0到k-1之间（一共有k种可能的取值），且k不太大时（k = O(n)），就可以选择计数排序。
因为每个数字都是d位的，所以需要进行d轮中间排序，又每一次中间排序都采用的是计数排序，时间复杂度为θ(n+k)，故一共所需的时间耗费为θ(d(n+k))。

当d为常数，k = O(n)时，基数排序有线性运行时间。

（2）给定n个b位数和任何正整数r(r≤b)，RADIX-SORT能在θ((b/r)(n+2^r))时间内正确地对这些数进行排序。

该定理是体现出——我们在对每个关键字如何分解成若干数位这一方面，可以灵活选择。

因为本来数的划分就是灵活的，拿2进制的比特串举例，我们并不一定只能每一位每一位地对其进行读数和运算，按照不同数位进行组合我们就能得到八进制、十六进制…

比如说一个32位的字，我们可以看成是4个8位数，将每8个数字看成是一个单元(每一个数字都包含8位)，所以b = 32，r = 8，k = 2^r-1 = 255,d = b / r = 4,基数排序需要经过d = 4轮计数排序，而每一轮计数排序都需要耗费θ(n+k) = θ(n+2^r)。

对于一个值r≤b，将每个关键字看做是有d = (b / r)取上整个数字，每个数字都包含r位（实际上基于2^r进制得到了一些数字）。每一个数字都是界于0到2^r-1之间的一个整数，这样就可以采用计数排序，此处k = 2^r - 1.

四. 桶排序

1. 排序思想

（1）输入假设

桶排序和计数排序一样，都对输入做出了某种假设，因而可以运行得很快。

• 计数排序

假设输入是由一个小范围内的整数构成

• 桶排序

输入由一个随机过程产生，该过程将元素均匀地分布在某一范围内。

（2）排序思想

将区间范围(通常是[0,1))划分成n个相同大小的子区间，或称桶。然后，将n个输入数分布到各个桶中去。因为输入数据是均匀分布的，所以各个桶内的数据分布应该是较为均衡的。

为了得到最终的排序结果，先对各个桶中的数进行排序，然后按照次序把各个桶中的元素列出来。

2. 算法实现

• 输入数据：A[]，含有n个元素的数组A，且每个元素满足0≤A[i]＜1.
• 辅助数组：B[0…n-1]，用于存放桶（通常使用链表实现，因为存在大量数据插入操作）
• 输出数据：排序号的数据数组

（1）伪代码

[1]：遍历数组元素，将其按照某种规则散列到各个桶中。（哈希表原理）
[2]：在各个桶内进行元素排序，自主选择排序算法
[3]：按序将各个桶内的数据进行合并

（2）C++实现

#include<bits/stdc++.h>
using namespace std;
vector<int> data;

void bucketsort(vector<int> &data){
	int maxe = *max_element(data.begin(),data.end());
	int mine = *min_element(data.begin(),data.end());
	int d = maxe-mine;//区间总长度
	vector<vector<int> > bucketvec;//内层vector代表每一个桶，外层vector存放所有桶
	bucketvec.resize(data.size());//桶的最大个数就是元素个数
	
	//遍历元素，进行散列
	for(int i = 0;i<data.size();i++){
		int val = data[i];
		int index = (val - mine) / (d / data.size()-1);//计算桶索引
		bucketvec[index].push_back(val); 
	} 
	
	vector<int> sorted_vec;//用于存放排序结果的辅助空间
	 
	//各个桶内进行排序，底层实现可以自己根据实际问题采用不同算法
	for(int i = 0;i<bucketvec.size();i++){
		vector<int> buc = bucketvec[i];
		sort(buc.begin(),buc.end());
		sorted_vec.insert(sorted_vec.end(),buc.begin(),buc.end());
		//采用尾插 
	}
	data = sorted_vec; 
	 
} 

int main(){//测试程序 
    for(int i = 0;i<10;i++){
    	int tmp;
    	cin>>tmp;
    	data.push_back(tmp);
	}
	cout<<"排序前的数值:"<<endl;
	for(int i = 0;i<10;i++)
	    cout<<data[i]<<" ";
	cout<<endl;
	bucketsort(data);
	cout<<"排序后的数值:"<<endl;
	for(int i = 0;i<10;i++)
	    cout<<data[i]<<" ";
	cout<<endl;
	return 0; 
}