Beyond the Void
BYVoid
三种线性排序算法 计数排序、桶排序与基数排序

[非基于比较的排序]

在计算机科学中,排序是一门基础的算法技术,许多算法都要以此作为基础,不同的排序算法有着不同的时间开销和空间开销。排序算法有非常多种,如我们最常用的快速排序和堆排序等算法,这些算法需要对序列中的数据进行比较,因为被称为基于比较的排序

基于比较的排序算法是不能突破O(NlogN)的。简单证明如下:

N个数有N!个可能的排列情况,也就是说基于比较的排序算法的判定树有N!个叶子结点,比较次数至少为log(N!)=O(NlogN)(斯特林公式)。

非基于比较的排序,如计数排序,桶排序,和在此基础上的基数排序,则可以突破O(NlogN)时间下限。但要注意的是,非基于比较的排序算法的使用都是有条件限制的,例如元素的大小限制,相反,基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用,对于特定场合有着特殊的性质数据,非基于比较的排序算法则能够非常巧妙地解决。

本文着重介绍三种线性的非基于比较的排序算法:计数排序、桶排序与基数排序。

[计数排序]

首先从计数排序(Counting Sort)开始介绍起,假设我们有一个待排序的整数序列A,其中元素的最小值不小于0,最大值不超过K。建立一个长度为K的线性表C,用来记录不大于每个值的元素的个数。

算法思路如下:

  1. 扫描序列A,以A中的每个元素的值为索引,把出现的个数填入C中。此时C[i]可以表示A中值为i的元素的个数。
  2. 对于C从头开始累加,使C[i]<-C[i]+C[i-1]。这样,C[i]就表示A中值不大于i的元素的个数
  3. 按照统计出的值,输出结果。

由线性表C我们可以很方便地求出排序后的数据,定义B为目标的序列,Order[i]为排名第i的元素在A中的位置,则可以用以下方法统计。

/*
 * Problem: Counting Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:27
 * State: Solved
 * Memo: 计数排序
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
	int *C=new int[K+1];
	int i;
	memset(C,0,sizeof(int)*(K+1));
	for (i=1;i<=N;i++) //把A中的每个元素分配
		C[A[i]]++;
	for (i=2;i<=K;i++) //统计不大于i的元素的个数
		C[i]+=C[i-1];
	for (i=N;i>=1;i--)
	{
		B[C[A[i]]]=A[i]; //按照统计的位置,将值输出到B中,将顺序输出到Order中
		Order[C[A[i]]]=i;
		C[A[i]]--;
	}
}
int main()
{
	int *A,*B,*Order,N=15,K=10,i;
	A=new int[N+1];
	B=new int[N+1];
	Order=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的随机数
	printf("Before CS:\n");
	for (i=1;i<=N;i++)
		printf("%d ",A[i]);
	CountingSort(A,B,Order,N,K);
	printf("\nAfter CS:\n");
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	printf("\nOrder:\n");
	for (i=1;i<=N;i++)
		printf("%d ",Order[i]);
	return 0;
}

程序运行效果如下:

Before CS:
2 8 5 1 10 5 9 9 3 5 6 6 2 8 2
After CS:
1 2 2 2 3 5 5 5 6 6 8 8 9 9 10
Order:
4 1 13 15 9 3 6 10 11 12 2 14 7 8 5

显然地,计数排序的时间复杂度为O(N+K),空间复杂度为O(N+K)。当K不是很大时,这是一个很有效的线性排序算法。更重要的是,它是一种稳定排序算法,即排序后的相同值的元素原有的相对位置不会发生改变(表现在Order上),这是计数排序很重要的一个性质,就是根据这个性质,我们才能把它应用到基数排序。

[桶排序]

可能你会发现,计数排序似乎饶了点弯子,比如当我们刚刚统计出C,C[i]可以表示A中值为i的元素的个数,此时我们直接顺序地扫描C,就可以求出排序后的结果。的确是这样,不过这种方法不再是计数排序,而是桶排序(Bucket Sort),确切地说,是桶排序的一种特殊情况。

用这种方法,可以很容易写出程序,比计数排序还简单,只是不能求出稳定的Order。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:32
 * State: Solved
 * Memo: 桶排序特殊实现
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void BucketSort(int *A,int *B,int N,int K)
{
	int *C=new int[K+1];
	int i,j,k;
	memset(C,0,sizeof(int)*(K+1));
	for (i=1;i<=N;i++) //把A中的每个元素按照值放入桶中
		C[A[i]]++;
	for (i=j=1;i<=K;i++,j=k) //统计每个桶元素的个数,并输出到B
		for (k=j;k<j+C[i];k++)
			B[k]=i;
}
int main()
{
	int *A,*B,N=1000,K=1000,i;
	A=new int[N+1];
	B=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的随机数
	BucketSort(A,B,N,K);
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	return 0;
}

这种特殊实现的方式时间复杂度为O(N+K),空间复杂度也为O(N+K),同样要求每个元素都要在K的范围内。更一般的,如果我们的K很大,无法直接开出O(K)的空间该如何呢?

首先定义桶,桶为一个数据容器,每个桶存储一个区间内的数。依然有一个待排序的整数序列A,元素的最小值不小于0,最大值不超过K。假设我们有M个桶,第i个桶Bucket[i]存储i*K/M至(i+1)*K/M之间的数,有如下桶排序的一般方法:

  1. 扫描序列A,根据每个元素的值所属的区间,放入指定的桶中(顺序放置)。
  2. 对每个桶中的元素进行排序,什么排序算法都可以,例如快速排序。
  3. 依次收集每个桶中的元素,顺序放置到输出序列中。

对该算法简单分析,如果数据是期望平均分布的,则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序,每次排序的时间复杂度为O(N/M*log(N/M))。则总的时间复杂度为O(N)+O(M)*O(N/M*log(N/M)) = O(N+ N*log(N/M)) = O(N + N*logN - N*logM)当M接近于N是,桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多,时间效率就越高,而桶越多,空间却就越大,由此可见时间和空间是一个矛盾的两个方面。

桶中元素的顺序放入和顺序取出是有必要的,因为这样可以确定桶排序是一种稳定排序算法,配合基数排序是很好用的。

/*
 * Problem: Bucket Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 桶排序一般实现
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct linklist
{
	linklist *next;
	int value;
	linklist(int v,linklist *n):value(v),next(n){}
	~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
/*
为了方便,我把A中元素加入桶中时是倒序放入的,而收集取出时也是倒序放入序列的,所以不违背稳定排序。
*/
void BucketSort(int *A,int *B,int N,int K)
{
	linklist *Bucket[101],*p;//建立桶
	int i,j,k,M;
	M=K/100;
	memset(Bucket,0,sizeof(Bucket));
	for (i=1;i<=N;i++)
	{
		k=A[i]/M; //把A中的每个元素按照的范围值放入对应桶中
		Bucket[k]=new linklist(A[i],Bucket[k]);
	}
	for (k=j=0;k<=100;k++)
	{
		i=j;
		for (p=Bucket[k];p;p=p->next)
			B[++j]=p->value; //把桶中每个元素取出,排序并加入B
		delete Bucket[k];
		qsort(B+i+1,j-i,sizeof(B[0]),cmp);
	}
}
int main()
{
	int *A,*B,N=100,K=10000,i;
	A=new int[N+1];
	B=new int[N+1];
	for (i=1;i<=N;i++)
		A[i]=rand()%K+1; //生成1..K的随机数
	BucketSort(A,B,N,K);
	for (i=1;i<=N;i++)
		printf("%d ",B[i]);
	return 0;
}

[基数排序]

下面说到我们的重头戏,基数排序(Radix Sort)。上述的基数排序和桶排序都只是在研究一个关键字的排序,现在我们来讨论有多个关键字的排序问题。

假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常,基数排序要用到计数排序或者桶排序。使用计数排序时,需要的是Order数组。使用桶排序时,可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序:

/*
 * Problem: Radix Sort
 * Author: Guo Jiabao
 * Time: 2009.3.29 16:50
 * State: Solved
 * Memo: 基数排序 结构数组
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
	int key[2];
};
struct linklist
{
	linklist *next;
	data value;
	linklist(data v,linklist *n):value(v),next(n){}
	~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
	linklist *Bucket[101],*p;//建立桶
	int i,j,k,M;
	M=K/100+1;
	memset(Bucket,0,sizeof(Bucket));
	for (i=1;i<=N;i++)
	{
		k=A[i].key[y]/M; //把A中的每个元素按照的范围值放入对应桶中
		Bucket[k]=new linklist(A[i],Bucket[k]);
	}
	for (k=j=0;k<=100;k++)
	{
		for (p=Bucket[k];p;p=p->next) j++;
		for (p=Bucket[k],i=1;p;p=p->next,i++)
			A[j-i+1]=p->value; //把桶中每个元素取出
		delete Bucket[k];
	}
}
void RadixSort(data *A,int N,int K)
{
	for (int j=1;j>=0;j--) //从低优先到高优先 LSD
		BucketSort(A,N,K,j);
}
int main()
{
	int N=100,K=1000,i;
	data *A=new data[N+1];
	for (i=1;i<=N;i++)
	{
		A[i].key[0]=rand()%K+1;
		A[i].key[1]=rand()%K+1;
	}
	RadixSort(A,N,K);
	for (i=1;i<=N;i++)
		printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
	printf("\n");
	return 0;
}

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等。

对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序

[三种线性排序算法的比较]

从整体上来说,计数排序,桶排序都是非基于比较的排序算法,而其时间复杂度依赖于数据的范围,桶排序还依赖于空间的开销和数据的分布。而基数排序是一种对多元组排序的有效方法,具体实现要用到计数排序或桶排序。

相对于快速排序、堆排序等基于比较的排序算法,计数排序、桶排序和基数排序限制较多,不如快速排序、堆排序等算法灵活性好。但反过来讲,这三种线性排序算法之所以能够达到线性时间,是因为充分利用了待排序数据的特性,如果生硬得使用快速排序、堆排序等算法,就相当于浪费了这些特性,因而达不到更高的效率。

在实际应用中,基数排序可以用于后缀数组的倍增算法,使时间复杂度从O(N*logN*logN)降到O(N*logN)。线性排序算法使用最重要的是,充分利用数据特殊的性质,以达到最佳效果

BYVoid 原创讲解,转载请注明。


上次修改时间 2017-05-22

相关日志