桶並べ替えjava版

もう一つの線形時間の並べ替えアルゴリズム。線形並べ替えアルゴリズムの思考については、プログラム珠玉第一章の内容を見てもいいです。アルゴリズムの問題を検討する時は、問題のデータの構造と分布状況をよく分析して、桶の順序付けは均一分布を入力して性能を発揮します。
コード:

package com.xingzhe.bucketsort;
import java.util.ArrayList;
/**
 *    ，                       a[i]   0<=a[i]<1
 *
 * @author Hercules
 *
 */
public class BucketSort {
    public static void bucket_sort(double[] a) {
        //     
        int length = a.length;
        //            length     ，         ，  java      ，  ArrayList   
        ArrayList<ArrayList<Double>> b = new ArrayList<ArrayList<Double>>();
        //  “  ”             
        for (int i = 0; i < a.length; i++) {
            b.add(new ArrayList<Double>());
        }
        //                      
        for (int i = 0; i < a.length; i++) {
            b.get((int) Math.floor(length * a[i])).add(a[i]);
        }
        //            
        for (int i = 0; i < a.length; i++) {
            insert_sort(b.get(i));
        }
        //                   
        int ai = 0;
        for (int i = 0; i < b.size(); i++) {
            if (b.get(i).size() == 0) {
                continue;
            }
            for (int j = 0; j < b.get(i).size(); j++) {
                a[ai++] = b.get(i).get(j);
            }
        }
    }
    /*
     *        
     */
    private static void insert_sort(ArrayList<Double> array) {
        if (array.size() == 0)
            return;
        for (int j = 1; j < array.size(); j++) {
            double key = array.get(j);
            int i = j - 1;
            while (i >= 0 && array.get(i) > key) {
                array.set(i + 1, array.get(i));
                i--;
            }
            array.set(i + 1, key);
        }
    }
    public static void main(String[] args) {
        double[] a = new double[] { 0.25, 0.36, 0.25, 0.65, 0.18, 0.48, 0.27,
                0.29, 0.24, 0.75 };
        bucket_sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}