`

算法回顾之八:基数排序

 
阅读更多

算法回顾系列第八篇:基数排序

--------------------------------

基数排序

 

基本原理:

顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

 

程序实现:

/**
 * RadixSort:
 * 分为LSD(Least significant digital)或MSD(Most significant digital),
 * LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始.
 */
public class RadixSort{
	
	/**
	 * LSD方式(由键值的最右边开始)
	 * 由于先做了低位的排序,所以当高位相等时,低位数字还是由小到大的顺序入桶的,就是说入完桶还是有序的.
	 * @param 待排序数组
	 * @param 桶个数(即Hash后存在多少种情况),此处因为是数字,所以共需要0-9个桶.
	 */
	public static void lsdSort(int[] number,int d){
		//temp[桶个数][桶内元素个数](桶内元素最多可能是全部元素)
		int[][] temp = new int[d][number.length];
		//每个桶内元素的计数
		int[] order = new int[d];
		int maxLength = getMaxNumberLength(number);//该数组内元素的最大位数.
		int current=1;//控制键值排序依据哪一位(LSD从最右起).
		int currentValue=1;//位数代表的值(1-个位,10-十位,100-百位...)
		int k=0;//用于标记将桶内元素复制到数组中的位置.
		while(current <= maxLength) {
			System.out.println("********************");
			System.out.println("当前位:"+current+" 代表值:"+currentValue);
			System.out.println("入桶:");
			for(int i = 0; i < number.length; i++){
				//Hash取放入哪个桶:除以所在位数值,再与桶总数取模(即第几个桶).
				int lsd = ((number[i] / currentValue) % d);
				//放入桶内哪个位置采用计数法.
				temp[lsd][order[lsd]] = number[i];
				//放入桶后该桶内元素计数加1.
				order[lsd]++;
			}
			System.out.println("各桶内元素分布:"+Arrays.deepToString(temp));
			System.out.println("各桶内元素计数:"+Arrays.toString(order));
			System.out.println("出桶:");
			for(int i = 0; i < d; i++){//顺序遍历各桶.
				if(order[i] != 0){//如果桶内元素个数不为0.
					for(int j = 0; j < order[i]; j++) {//遍历当前桶内元素.
						number[k] = temp[i][j];//将当前桶内元素整理到数组中.
						k++;//标记位右移;
						temp[i][j]=0;//复制后桶内元素清0.
					}
				}
				order[i] = 0;//每个桶内元素复制完后,桶内元素计数清0.
			}
			System.out.println("本趟出桶整理后:"+Arrays.toString(number));
			current++;
			currentValue *= 10;//LSD方式每左移一位,该位代表的值*10.
			k = 0;//每趟复制结束后,标记位归0.
		}
	}
	
	/**
	 * 取数组内元素的最大长度
	 */
	public static int getMaxNumberLength(int[] number){
		int maxLength = 1;//最大数字长度
		for(int i=0;i<number.length;i++){
			int length;//当前数字长度
			int k=1;//倍数
			//每次循环递增10倍,一直除到0为止.
			for(length=0;(number[i]/k)>0;length++){
				k*=10;
			}
			if(length>maxLength){
				maxLength=length;
			}
		}
		return maxLength;
	}
	
	public static void main(String[] args) {
		int[] data = new int[]{73,22,93,43,55,14,28,65,39,81,33,100,6};
		RadixSort.lsdSort(data, 10);
		System.out.println("Result:"+Arrays.toString(data));
	}
}

上面程序中:

从右向左依次作为排序依据位放入桶中,并记录每个桶内的元素个数。

然后,按桶的顺序将桶内元素写入排序数组内。

依此类推,直到最高位完成排序。

 

由于先做了低位的排序,所以当高位相等时,低位数字还是由小到大的顺序入桶的,就是说入完桶还是有序的。

 

性能分析:O(d(n+radix)),n个记录,d个关键码,关键码的取值范围为radix.

 

空间复杂度:O(n)

稳定性:稳定。

分享到:
评论

相关推荐

    数据结构实验报告--链式基数排序算法.doc

    链式基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在描述中提到的实验报告中,主要目标是实现一个链式基数排序算法,用于对一组数据进行最低位优先的排序...

    实验五:内部排序.docx

    - 基数排序:非比较排序,利用多关键字思想,如基数排序,时间复杂度为 O(n)。 2. **时间复杂度与排序方法**: - 时间复杂度为 O(n^2) 的排序方法:直接插入排序、直接选择排序、冒泡排序,简单易懂但效率较低。 ...

    算法导论课后习题与思考题答案合集

    - **第8章:线性时间排序**:讨论基数排序、计数排序和桶排序等线性时间排序算法。 - **第9章:中位数与顺序统计量**:介绍如何有效地找到一个数组中的中位数或任意顺序统计量。 - **第11章:哈希表**:讲解哈希...

    数据结构和算法-思维导图.pdf

    - 各种排序算法如冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序和计数排序的时间复杂度。 - 排序算法的稳定性,例如快速排序是不稳定的,而归并排序是稳定的。 3. **字符串处理...

    算法导论-教师用书英文版

    - **基数排序**:讲解基数排序的机制,特别是适用于非负整数的情况。 - **桶排序**:讨论桶排序的工作原理及其优势。 **第九章:中位数与序统计数** - **中位数的概念**:解释中位数的定义及其在数据处理中的重要性...

    算法分析与设计 叫我们如何设计更多好程序

    本文将深入探讨两种经典的排序算法——计数排序(Counting Sort)和基数排序(Radix Sort),以及它们在算法分析中的重要性。 首先,让我们回顾一下比较排序。比较排序是一种基于元素之间比较来确定顺序的排序算法...

    数据结构第九章排序讲稿.doc

    8. **基数排序**:基数排序是一种非比较型排序,根据数字的每一位进行排序,尤其适合于整数排序。它的时间复杂度为O(kn),其中k是数字的最大位数。 9. **各种排序方法比较**:在选择合适的排序算法时,我们需要考虑...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    6.5.2 基数排序 6.5.3 凸包 6.5.4 并查集 第7章 数组和矩阵 7.1 数组 7.1.1 抽象数据类型 7.1.2 C++数组的索引 7.1.3 行主映射和列主映射 7.1.4 用数组的数组来描述 7.1.5 行主描述和列主描述 7.1.6 不规则二维数组 ...

    C语言版数据结构与算法分析-严蔚敏经典视频教程

    06-003习题课:栈的基本操作、KMP算法回顾 06-004二叉树的定义、性质与存储结构 06-005二叉树的前序、中序和后序遍历的递归与非递归算法 06-006统计二叉树中叶子结点个数、按给定的先序序列建立二叉链表 06-007线索...

    数据结构与算法课程总结

    循环队列的空满判断和基数排序是挑战点。 第六章“特殊矩阵、广义表及其应用”探讨了数组、稀疏矩阵和广义表。特殊矩阵的压缩存储和广义表的运算算法是关键,而稀疏矩阵的计算和广义表的操作理解需要加强。 第七章...

    数据结构与算法:C++描述

    3.8.2 基数排序 116 3.8.3 等价类 117 3.8.4 凸包 122 3.9 参考及推荐读物 127 第4章 数组和矩阵 128 4.1 数组 128 4.1.1 抽象数据类型 128 4.1.2 C++数组 129 4.1.3 行主映射和列主映射 129 4.1.4 类Array1D 131 ...

    leetcode叫数-Algorithm:从LeetCode学习算法和解决算法问题

    leetcode叫数 结构 list 链表 recursive 递归 sort 排序 stack 栈 ...需要回顾 ...冒泡和选择排序不要混淆了,插入排序...基数排序:基数排序要求数据可以划分成高低位,位之间有递进关系,用稳定排序算法依次按低位到高位排

    算法:竞争性编程所需的算法

    内容:搜索算法线性搜寻二进制搜索三元搜索排序算法气泡排序选择排序插入排序合并排序快速分类基数排序Bogo排序最短路径算法迪克斯特拉弗洛伊德·沃沙尔通用数据结构堆队列叠数组链表使用的语言: C ++ PythonJavaC ...

    he Art Of Computer Programming Volume 4 Donald E Knuth

    - 高级排序技术,如基数排序、桶排序等。 - 各种搜索策略,包括线性搜索、二分搜索等。 - 散列函数的设计与实现,以及如何优化散列表性能。 ##### 数据结构 - **定义与背景**:数据结构是计算机科学中的一个...

    2012-2013山大软件数据结构期末试题(真题)回顾

    基数排序是根据数字的每一位进行排序,不依赖元素间的相对顺序;堆排序利用堆的性质,只关心最大或最小元素的位置,与初始顺序无关。 二、散列表: 2. 散列表是一种通过散列函数将数据映射到固定地址空间的数据结构...

    leetcode中国-practice:每日伸展运动

    基数排序 插入排序 TODO:尾调用优化空间? 大型系统分布式系统 不同排序算法的比较 问题: nodejs 中可能存在 ** 兼容性问题 类别: 树动态规划回溯 排序图 学习资源 动态规划 涵盖的问题 二维 DP 濒海战斗舰 给定...

Global site tag (gtag.js) - Google Analytics