【数据结构】中的基数排序(BucketSort)

男娘i 2022-06-15 02:11 132阅读 0赞

基数排序的概念：

基数[排序法][Link 1]又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其[时间复杂度][Link 2]为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。

画图描述：

![Center][]![Center 1][]

![Center 2][]

![Center 3][]

![Center 4][]

基数排序的代码：

//MSD：由高位到个位，排低位时要排上一个位相同的元素（否则会影响上一个位的排序结果）
    //LSD：由个位到高位
    #include<iostream>
    using namespace std;
    #include<assert.h>
    #pragma once
    
    size_t GetMaxDigit(size_t *a, size_t n)
    {
    	size_t digit = 1;
    	size_t base = 10;
    	for (size_t i = 0; i < n; i++)
    	{
    		while (a[i] >= base)
    		{
    			base *= 10;
    			digit++;
    		}
    	}
    	return digit;
    }
    
    
    void LSDSort(size_t *a, size_t n)
    {
    	size_t maxDigit = GetMaxDigit(a, n);
    	size_t base = 1;
    
    	size_t *bucket = new size_t[n];
    	while ((maxDigit--) > 0)
    	{
    		size_t counts[10] = { 0 };
    		size_t start[10] = { 0 };
    		start[0] = 0;
    
    		for (size_t i = 0; i < n; i++)
    		{
    			size_t num = (a[i] / base) % 10;
    			counts[num]++;
    		}
    		for (size_t i = 1; i < 10; i++)
    		{
    			start[i] = start[i - 1] + counts[i - 1];
    		}
    
    		for (size_t i = 0; i < n; i++)
    		{
    			size_t num = (a[i] / base) % 10;
    			bucket[start[num]++] = a[i];
    		}
    		memcpy(a, bucket, sizeof(size_t)*n);
    		base *= 10;
    	}
    }
    
    void printArray(size_t *a, size_t n)
    {
    	for (size_t i = 0; i < n; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    int main()
    {
    	//size_t arr[] = { 1, 3, 5, 7, 0, 2, 9, 4, 6, 8 };
    	size_t arr[] = { 49, 38, 65, 97, 76, 13, 27, 49, 50, 77 };
    	size_t n = sizeof(arr) / sizeof(arr[0]);
    	cout << "进行基数排序前：";
    	printArray(arr, n);
    	LSDSort(arr, n);
    	cout << "进行基数排序后：";
    	printArray(arr, n);
    	system("pause");
    	return 0;
    }

运行结果如下：

![Center 5][]

[Link 1]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=8660203&ss_c=ssc.citiao.link
[Link 2]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=105680&ss_c=ssc.citiao.link
[Center]: https://img-blog.csdn.net/20170521010107452?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFgxODc5MjczMjEyNw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220615/ac41a064375c4ca3ac2e619a8d6cd874.png
[Center 2]: /images/20220615/8ebdce39ae67486a9c97c1f9f68ec51c.png
[Center 3]: /images/20220615/eb866822fe8c48f5810ddb68d673e654.png
[Center 4]: /images/20220615/c3ee385131fb495e9f7b57c7ddcfb03f.png
[Center 5]: /images/20220615/91c455044e8d4018af74bb8a63aa2a1c.png