现在的位置: 首页 > 综合 > 正文

桶排序

2014年02月20日 ⁄ 综合 ⁄ 共 1072字 ⁄ 字号 评论关闭

/**
 * 桶排序 
 */
public class TongPaixu {
	 
	public class BucketSortTest {

	    public static int count = 0;
	    
	    public void main(String[] args) {
	        int[] data= new int[] { 5, 3, 6, 2, 1, 9, 4, 4, 4, 8, 7 };

	       print(data);

	       bucketSort(data, 0, 10);

	       print(data);

	    }

	    public void bucketSort(int[] data, int min, int max) {

	        // 缓存数组
	        int[] tmp =new int[data.length];
	        // buckets用于记录待排序元素的信息
	        // buckets数组定义了max-min个桶
	        int[]buckets = new int[max - min];

	        // 计算每个元素在序列出现的次数
	        for (int i= 0; i < data.length; i++) {
	           buckets[data[i] - min]++;
	        }

	        // 计算“落入”各桶内的元素在有序序列中的位置
	        for (int i= 1; i < max - min; i++) {
	           buckets[i] = buckets[i] + buckets[i - 1];
	        }

	        // 将data中的元素完全复制到tmp数组中
	        System.arraycopy(data, 0, tmp, 0, data.length);

	        // 根据buckets数组中的信息将待排序列的各元素放入相应位置

	        for (int k= data.length - 1; k >= 0; k--) {
	           data[--buckets[tmp[k] - min]] = tmp[k];

	        }
	    }

	    public void print(int[] data) {
	        for (int i= 0; i < data.length; i++) {
	           System.out.print(data[i] + "\t");
	        }

	       System.out.println();
	    }
	 

	}
}

参考链接:

http://www.cnblogs.com/sun/archive/2008/07/07/1237331.html

http://hxraid.iteye.com/blog/647759

http://blog.csdn.net/houapple/article/details/6480100

http://blog.csdn.net/xieyuntestshow/article/details/7063749

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.6.1.2.htm

抱歉!评论已关闭.