排序算法笔记:基数排序 RadixSort in java
博客专区 > CheN_exe 的博客 > 博客详情
排序算法笔记:基数排序 RadixSort in java
CheN_exe 发表于4年前
排序算法笔记:基数排序 RadixSort in java
  • 发表于 4年前
  • 阅读 106
  • 收藏 4
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

/**
 * 基数排序
 * 简述:
 * 		先按照个位排序,将结果串起,再按照十位排序,再将数字串起,再按照排序...
 * 时间复杂度:
 * 		当k=O(n)时,O(n)
 * 空间复杂度:
 * 		O(n)
 * 优点:
 * 		
 * 缺点:
 * 		要求全为自然数
 * 可改进:
 * 		可以自建Map或List,将字母顺序加入,则可以进行更多种类排序.但是小数比较麻烦
 * @author CheN
 *
 */
public class RadixSort {
	
	public static int[] asc( int[] array ){
		int index = 1; // 最大数字位数(如100为3位数字,2000为4位数字)
		// 取得最大数字位数
		for( int i = 0 ; i < array.length ; i++ ){
			int length = Integer.toString(array[i]).length();
			if( index < length ){
				index = length;
			}
		}
		return sort( array , 0 , index);
	}
	
	/**
	 * @param array 数组
	 * @param exponent 起始位数(代码中实际意义为:10的exponent次方。起始位数即为10的0次方,所以为个位) 
	 * @param index 最大数字位数(如100为3位数字,2000为4位数字)
	 * @return
	 */
	private static int[] sort( int[] array , int exponent , int index){
		int length = array.length;
		// 此处我选择用List,而不是int[n][n]的数组
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for( int i = 0 ; i < 10  ; i++ ){
			list.add(new ArrayList<Integer>());
		}
		// 按照各个位数排序统计
		for( int i = 0 ; i < length ; i++ ){
			int num = 0;
			String str = Integer.toString(array[i]);
			if( str.length() - exponent - 1 >= 0 )
				num = Integer.parseInt(str.substring(str.length() - exponent - 1, str.length() - exponent));
			list.get(num).add(array[i]);
		}
		// 串起桶中数据
		for( int k = 0 , i = 0 ; i < list.size() ; i++ ){
			for( int j = 0 ; j < list.get(i).size() ; j++ ){
				array[ k++ ] = list.get(i).get(j);
			}
		}
		// 若还有更高位数,则按照下一位数进行排序
		if( index == ++exponent ){
			return array;
		}else{
			return sort( array , exponent , index );
		}
	}
}

 


若有错误或不妥之处,敬请谅解并指点。

共有 人打赏支持
粉丝 3
博文 31
码字总数 16641
×
CheN_exe
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: