`
北极的。鱼
  • 浏览: 162926 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

【转】基数排序

 
阅读更多

转自:http://blog.csdn.net/weiwenhp/article/details/8617417

 

我们知道假如一个正整数A大于数B,要么就是A的位数更多点,要是相同位数则从高往低数起,必有某一位大于B.

基数排序就是把一待排序的元素每一位(个,十,百...)拆分出来排序.先从个位,然后再十位.那么首先肯定要确定下待排序中的元素最大数有多少位.然后再借助一个临时数组和一个计数的大小为10的数组辅助每一轮的排序。

请参考计数排序

//先计算出待排序元素最大数的位数

int MaxDigit(int* arr, int len)
{
	int digit = 1;   //所有元素小于10时的默认最大位数为1
	int radix = 10;
	for (int i = 0; i < len; i++) //遍历整个序列
	{
		if (arr[i] >= 10)
		{
			while (arr[i] >= radix)  //当大于等于10则最大位数为2,依此类推大于等于100是3
			{
				digit++;
				radix = radix * 10;
			}
		}
	}
	return digit;
}



void RadixSort(int* arr, int len)
{
	int digit = MaxDigit(arr, len);  //待排序数组最大元素的位数为digit
	int* tmpArr = new int[len];  //辅助排序的临时数组
	int count[10] = { 0 };        //索引0 - 9刚好对应数字0至9
	int radix = 1;
	int val;  //计算出来的元素每一位的值
	for (int i = 1; i <= digit; i++) //i是1时对个位数排序,为2时对百位数排序
	{
		for (int j = 0; j < 10; j++)//初始化count数组为0
			count[j] = 0;
		
		for (int j = 0; j < len; j++)
		{
            //计算每一位的数值,当radix为1时是个位,为100时是百位数的值
			val = (arr[j] / radix) % 10; 
            //val的值是索引0-9,每有一位元素的位数值与索引值相同则计数数组索引对应值加1
			count[val] ++; 
		}
				
		//这一步最为关键,很让人迷糊的.我们经过前面一步后,数组中每个索引对应的值是arr元素的个数.
		//要是把计数数组count中所有值加起来,总数应该是len.
        //现在用前一个值是自己本身的值相加得出的结果是左边所有
		//元素个数和,这在等会映射到tmpArr中时有用
		for (int j = 1; j < 10; j++)
			count[j] = count[j - 1] + count[j];
		
		for (int j = len - 1; j >= 0; j--)//见备注
		{
			val = (arr[j] / radix) % 10;
			tmpArr[count[val] - 1] = arr[j]; //把arr的元素映射到tmpArr,且是按位数排好序的.
			count[val]--;
		}
		
		for (int j = 0; j < len; j++)
			arr[j] = tmpArr[j]; //把临时数组中按位排好序的元素拿回来
				
		radix = radix * 10;
	}
	delete[] tmpArr;
}

 备注:

这里要注意的是 “扫描a数组把各个元素放在有序序列相应的位置上” 这步为什么要从后往前扫描a数组呢?大家想一想计数排序的过程就知道,因为从前扫描导致计数排序不稳定,前面说了,计数排序是基数排序的基础,所以它的稳定性直接影响到基数排序的稳定。

分享到:
评论

相关推荐

    C++写基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...

    数据结构基数排序

    数据结构中的基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数...

    Radix Sort (基数排序)排序算法

    ### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...

    利用递归算法实现的基数排序算法

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。递归算法则是一种解决问题的方法,它解决问题的每一个子问题都是原问题的缩小版,直到子问题简单到可以直接...

    Algorithm-基数排序

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。基数排序的名称来源...

    对10进制数进行基数排序 数据结构

    ### 对10进制数进行基数排序的数据结构与算法实现 #### 1. 基数排序概述 基数排序是一种非比较型整数排序算法,它通过整数的各位数字来分配进桶的方式来进行排序。该算法对于固定大小的整数特别有效。基数排序的...

    lemon-guide-基数排序

    在计算机科学中,基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、浮点数等,基数排序也不是只能用于...

    python实现基数排序算法代码

    基数排序算法是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体实现时,从最低位开始,也就是个位数,然后是十位、百位等等,直到最高位。在每一趟排序中,使用的是...

    基数排序的Java实现方法RadixSort

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、日期等,所以基数排序并不是只能用于整数。 基数排序的Java实现方法RadixSort,...

    基数排序_DataStructure-RadixSort.zip

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。通常用的排序算法...

    基数排序_Countingsort.zip

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、算法中更确切地说是将数据中的每个数按照“基数”拆分成单个单位,然后从低位到...

    基数排序代码.docx

    基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...

    基数排序算法.zip

    基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法是通过分配、收集和再分配的步骤来实现的,它不依赖于元素之间的比较,而是依赖于数字的位数。这种...

    C++实现基数排序(源代码)

    ### C++实现基数排序 #### 一、基数排序概述 基数排序是一种非比较型的整数排序算法。它通过对整数的每一位进行排序来达到整体序列的有序化。该算法的特点在于它不是通过元素间的相互比较来进行排序,而是通过按...

    Java实现基数排序算法(源代码)

    ### Java实现基数排序算法 #### 实现原理 基数排序是一种非常高效的非比较型整数排序算法,它通过按数字的各个位数进行排序来实现序列的整体有序化。该算法的关键在于能够有效地处理多位数,避免了传统的两两比较...

    基数排序介绍和java代码实现

    基数排序是一种非比较型整数排序算法,它的核心在于将数字按位进行处理,从低位到高位逐位进行排序。这种排序方式适用于处理包含整数或者可以转换为整数形式的数据,如字符串。基数排序的关键在于“计数排序”...

    算法与数据结构,Java基数排序,归并排序,利用栈将四则表达式中缀转换为后缀并计算_Arithmetic.zip

    在探讨算法与数据结构的领域,Java编程语言提供了一种强大的工具来实现各种算法,其中包括基数排序和归并排序。基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较...

    链表基数排序的存储空间效率优化.pptx

    ### 链表基数排序的存储空间效率优化 #### 一、优化桶结构,降低空间消耗 在链表基数排序中,桶结构的选择对于优化存储空间有着至关重要的作用。优化桶结构可以从以下几个方面入手: 1. **基于哈希表的优化桶结构...

    对时间进行基数排序,输入的是整数格式、输出的是字符串形式

    ### 时间整数格式基数排序及转换为字符串形式 在计算机科学中,基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。基数排序通常用于那些不是通过比较元素大小来...

    java8中经典排序算法:插入排序、堆排序,选择排序、希尔排序,基数排序、

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。它的时间复杂度为O(nk),其中n是排序的数的个数,k是数的位数。当k不大时,基数排序的效率是很高的。 冒泡...

Global site tag (gtag.js) - Google Analytics