八大排序算法-基数排序

水深无声 2022-06-07 13:47 232阅读 0赞

基数排序（radix sort）

定义：

属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

分类：

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。  
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

基数排序基本思想：

第一步  
以LSD为例，假设原来有一串数值如下所示：  
73, 22, 93, 43, 55, 14, 28, 65, 39, 81  
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：  
0  
1 81  
2 22  
3 73 93 43  
4 14  
5 55 65  
6  
7  
8 28  
9 39  
第二步  
接下来将这些桶子中的数值重新串接起来，成为以下的数列：  
81, 22, 73, 93, 43, 14, 55, 65, 28, 39  
接着再进行一次分配，这次是根据十位数来分配：  
0  
1 14  
2 22 28  
3 39  
4 43  
5 55  
6 65  
7 73  
8 81  
9 93  
第三步  
接下来将这些桶子中的数值重新串接起来，成为以下的数列：  
14, 22, 28, 39, 43, 55, 65, 73, 81, 93  
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

时间效率\[1\]：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。   
空间效率：需要2\*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

算法：

#include "stdafx.h"
    #include "iostream"
    int arr[] = { 35, 28, 58, 10, 61, 58, 97, 17 };
    int k = sizeof(arr) / sizeof(arr[0]);
    
    int maxbit(int data[], int n) //辅助函数，求数据的最大位数
    {
    	int d = 1; //保存最大的位数
    	int p = 10;
    	for (int i = 0; i < n; ++i)
    	{
    		while (data[i] >= p)
    		{
    			p *= 10;
    			++d;
    		}
    	}
    	return d;
    }
    void radixsort(int data[], int n) //基数排序
    {
    	int d = maxbit(data, n);
    	int *tmp = 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 < 10; j++)
    			count[j] = 0; //每次分配前清空计数器
    		for (j = 0; j < n; j++)
    		{
    			k = (data[j] / radix) % 10; //统计每个桶中的记录数
    			count[k]++;
    		}
    		for (j = 1; j < 10; j++)
    			count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
    		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
    		{
    			k = (data[j] / radix) % 10;
    			tmp[count[k] - 1] = data[j];
    			count[k]--;
    		}
    		for (j = 0; j < n; j++) //将临时数组的内容复制到data中
    			data[j] = tmp[j];
    		radix = radix * 10;
    	}
    	delete[]tmp;
    	delete[]count;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	radixsort(arr, k);
    	for (int f = 0; f < k; f++)
    	{
    		std::cout << arr[f] << "  ";
    	}
    	getchar();
    	return 0;
    }