Java实现桶排序

2015/05/20 32145

清华大佬耗费三个月吐血整理的几百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]); 
        } 
    } 
   
}