清华大佬耗费三个月吐血整理的几百G的资源,免费分享!....>>>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | package linetimesort; import java.util.LinkedList; import sort.InsertSort; /** * 桶排序假设输入元素均匀而独立的分布在区间[0,1)上; * 桶排序的核心思想是,将[0,1)分为n个大小相同的子区间, * 上一个区间里的元素都比下一个区间里的元素小,然后对 * 所有区间里的元素排序,最后顺序输出所有区间里的元素, * 达到对所有元素排序的目的。 * @author yuncong * */ public class BucketSort { public void sort(Double[] a) { int n = a.length; /** * 创建链表(桶)集合并初始化,集合中的链表用于存放相应的元素 */ LinkedList<LinkedList<Double>> buckets = new LinkedList<>(); for ( int i = 0 ; i < n; i++){ LinkedList<Double> bucket = new LinkedList<>(); buckets.add(bucket); } // 把元素放进相应的桶中 for ( int i = 0 ; i < n; i++){ int index = ( int ) (a[i] * n); buckets.get(index).add(a[i]); } // 对每个桶中的元素排序,并放进a中 int index = 0 ; for (LinkedList<Double> linkedList : buckets) { int size = linkedList.size(); if (size == 0 ) { continue ; } /** * 把LinkedList<Double>转化为Double[]的原因是,之前已经实现了 * 对数组进行排序的算法 */ Double[] temp = new Double[size]; for ( int i = 0 ; i < temp.length; i++) { temp[i] = linkedList.get(i); } // 利用插入排序对temp排序 new InsertSort().sort(temp); for ( int i = 0 ; i < temp.length; i++) { a[index] = temp[i]; index++; } } } public static void main(String[] args) { Double[] a = new Double[]{ 0.3 , 0.6 , 0.5 }; new BucketSort().sort(a); for ( int i = 0 ; i < a.length; i++) { System.out.println(a[i]); } } } |