用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - java代码库

java桶式排序算法

2012-08-26 作者: 神马举报

[java]代码库

/**
 * 桶式排序:
 * 
 * 仅支持非负数排序!
 * 
 * 桶式排序不再是基于比较的了,它和基数排序同属于分配类的排序, 这类排序的特点是事先要知道待排 序列的一些特征。 桶式排序事先要知道待排
 * 序列在一个范围内,而且这个范围应该不是很大的。 比如知道待排序列在[0,M)内,那么可以分配M个桶,第I个桶记录I的出现情况,
 * 最后根据每个桶收到的位置信息把数据输出成有序的形式。 这里我们用两个临时性数组,一个用于记录位置信息,一个用于方便输出数据成有序方式,
 * 另外我们假设数据落在0到MAX,如果所给数据不是从0开始,你可以把每个数减去最小的数。
 */
public class BucketSort {
	public void sort(int[] keys, int from, int len, int max) {
		int[] temp = new int[len];
		int[] count = new int[max];

		for (int i = 0; i < len; i++) {
			count[keys[from + i]]++;
		}
		// calculate position info
		for (int i = 1; i < max; i++) {
			count[i] = count[i] + count[i - 1];// 这意味着有多少数目小于或等于i,因此它也是position+
												// 1
		}

		System.arraycopy(keys, from, temp, 0, len);
		for (int k = len - 1; k >= 0; k--)// 从最末到开头保持稳定性
		{
			keys[--count[temp[k]]] = temp[k];// position +1 =count
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] a = { 1, 4, 8, 3, 2, 9, 5, 0, 7, 6, 9, 10, 9, 13, 14, 15, 11, 12,
				17, 16 };
		BucketSort bucketSort = new BucketSort();
		bucketSort.sort(a, 0, a.length, 20);// 第四个参数为20,此参数必须比数组里最大值还要大,否则出错
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + ",");
		}

	}

}


网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...