排序算法——基数排序_基数排序平均时间

基数排序是通过“分配”和“收集”过程来实现排序。

（1）假设有欲排数据序列如下所示：

73  22  93  43  55  14  28  65  39  81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

81  22  73  93  43  14  55  65  28  39

接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：

分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：

14  22  28  39  43  55  65  73  81  93

观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。

 

基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），

LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。

注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

 

（1）MSD法实现

最高位优先法通常是一个递归的过程：

<1>先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。

<2>再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。

<3>依此重复，直到对关键码Kd完成排序为止。

<4> 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。

 

（2）LSD法实现

最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，

再依据次低位关键码Kd-1对上一趟排序的结果再排序，

依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。

使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。

 

现在使用扑克牌的例子说明一下这两种方法的差别：

我们把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。

要求如下：

花色顺序：梅花<方块<红心<黑桃

面值顺序：2<3<4<...<10<J<Q<K<A

那么，若要将一副扑克牌排成下列次序：

梅花2，...，梅花A，方块2，...，方块A，红心2，...，红心A，黑桃2，...，黑桃A。

有两种排序方法：

<1>先按花色分成四堆，把各堆收集起来；然后对每堆按面值由小到大排列，再按花色从小到大按堆收叠起来。----称为"最高位优先"(MSD)法。

<2>先按面值由小到大排列成13堆，然后从小到大收集起来；再按花色不同分成四堆，最后顺序收集起来。----称为"最低位优先"(LSD)法。

 

我们可以看出，基数排序的效率和初始序列是否有序没有关联。

平均时间复杂度：O(dn)(d即表示整形的最高位数)

空间复杂度：O(10n) （10表示0~9，用于存储临时的序列）  

算法稳定性：稳定 

在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。

基排序的C++实现代码：

#include<iostream>  
using namespace std;
 
//求数据的最大位数
int maxbit(int array[], int n)
{
	int d = 0;
	int i;
	int * temp = new int[n];
	for (i = 0; i < n; i++)
		temp[i] = array[i];
 
	for (i = 0; i < n; i++)
	{
		int p = 1;
		while (temp[i] / 10 > 0)
		{
			p++;
			temp[i] /= 10;
		}
		if (d < p)
			d = p;
	}
	delete[] temp;
	return d;
}
 
//基数排序
void radixSort(int data[], int n)//data数组中含有n=10个元素
{
	int d = maxbit(data, n);//求数组data中元素的最大位数
	int * temp = new int[n];
	int * count = new int[10]; //计数器
	int i, j, k;
 
	int radix = 1;
	for (i = 1; i <= d; i++)         //进行d次排序
	{
		for (j = 0; j < n; j++)
		{
			count[j] = 0;                //每次分配前清空计数器
		}
 
		for (j = 0; j < n; j++)
		{
			k = (data[j] / radix) % 10;              //统计每个桶中的记录数
			count[k]++;
		}
	
		for (j = 1; j < 10; j++)
		{
			//将temp中的位置依次分配给每个桶
			count[j] = count[j - 1] + count[j];
		}
 
		//将桶中的记录收集到temp中
		for (j = n - 1; j >= 0; j--)
		{
			k = (data[j] / radix) % 10;
			count[k]--;
			temp[count[k]] = data[j];
		}
 
		//将临时数组的内容复制到data中
		for (j = 0; j < n; j++)
		{
			data[j] = temp[j];
		}
		radix = radix * 10;
	}
 
	delete[] temp;
	delete[] count;
}
 
 
int main()
{
	int a[10] = { 265, 301, 751, 129, 937, 863, 742, 694, 76, 438 };
	int i, n = 10;
 
	cout << "排序前结果为: ";
	for (i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
 
	radixSort(a, n);           //调用基数排序函数
 
	cout << "排序后结果为: ";
	for (i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
 
	system("pause");
	return 0;
}

原理参考：http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html