×
文章路径: Java > 算法 > 排序

基数排序RadixSort与桶排序BucketSort

发表于3年前(Dec 24, 2014 10:21:45 AM)  阅读 731  评论 0

分类: Java 算法 排序

标签: bucketsort radixsort 基数排序 桶排序

基数排序:对于十进制数字来说,将要排序的数字对齐排成一列,我们可以从低位起,假设目标数组元素不超过3位,第一次我们把这列数字按个位数排序,在这基础上第二次我们把这些数字再按十位数排序,第三次按百位数排序,三趟下来得到的数组就是已排序的数组。在对个位数排序时,我们可以采用下面的方法,用10个标志为0..9的桶,桶0放入所有个位数为0的数,桶1放入所有个位数为1的数,最后将所有桶的数从桶0开始输出,这样得到的数组就是按个位数排序的数组。然后,其余高位数类似处理。

桶排序:其实基数排序已经用到了桶排序的思想。桶排序假设输入数组符合均匀发布,假设n个元素都是均匀而独立的分布在区间[0,1)上, 然后将区间[0,1)划分为n个相同大小的子区间,这些子区间就是桶,然后对桶中的元素进行排序(一般使用插入排序),最后输出桶中的元素,得到排序数组。桶排序假设输入均匀分布,所以一般每个桶中的元素不会很多,因而运行得很快。

桶排序算法很简单,在基数排序上做些小改动就行了,下面我只给出基数排序算法实现:

package sort;

/**
 * 基数排序
 * @author lihui
 *
 */
public class RadixSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = {
					329,
					457,
					657,
					839,
					436,
					720,
					355,
					1
				};
		radixSort(a, 3);
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+"\t");
		}
	}
	
	/**
	 * 
	 * @param a 待排序的数组
	 * @param d 数组中元素最大位数
	 */
	public static void radixSort(int[] a, int d) {
		//用来记录桶
		int[][] temp = new int[10][];
		//从低位排起,也可从高位排起
		for(int i=1;i<=d;i++) {
			//用来记录当前数字个数
			//nums[i]表示为temp中基数为i的数有nums[i]个
			int[] nums = new int[10];
			for(int j=0;j<a.length;j++) {
				//n为第d位上的数字
				int n = a[j]/((int)Math.pow(10, i));
				n = n%10;
				if(nums[n]==0) {
					temp[n] = new int[a.length];
				}
				nums[n]++;
				temp[n][nums[n]-1] = a[j];
			}
			int l = 0;
			//将d位排完序的数组连接放入原数组中
			for(int j=0;j<temp.length;j++) {
				for(int k=0;k<nums[j];k++) {
					a[l] = temp[j][k];
					l++;
				}
			}
		}
	}
	
}

基数排序跟桶排序的时间复杂度都是O(n)。

发表评论