Java實現桶排序

    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]);  
        }  
    }  

}  </pre>