思路原理

桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

过程

1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3. 将各个桶中的数据有序的合并起来

Data Structure Visualizations 提供了一个桶排序的分步动画演示。

代码

public class BucketSort {
    public static void main(String[] args) {
        int[] toBeSorted = { 3, 2, 1, 4, 6, 5 };

        int smin = 1, smax = 6;// 要排序的数里面最大的数
        int hashStep = 2;// 让一个桶中只能存连续的两个值的数，比如只能存a和a+1
        // 每个一维数组，即桶，的第一个元素表明这个桶里面的元素个数
        int[][] bucket = new int[(smax - smin + 1) / hashStep][toBeSorted.length + 1];
        for (int i = 0; i < bucket.length; i++) {
            // 桶的元素个数先置为0
            bucket[i][0] = 0;
        }

        for (int i = 0; i < toBeSorted.length; i++) {
            // 先将所有元素放到相应的桶里面，这个过程的时间复杂度为O(n)
            int bucketn = (toBeSorted[i] - smin) / hashStep;
            bucket[bucketn][bucket[bucketn][0] + 1] = toBeSorted[i];
            bucket[bucketn][0]++;// 桶内元素个数+1
            // 可以在放入桶的时候就对桶里的数进行排序，也可以之后再做
        }

        for (int i = 0; i < bucket.length; i++) {
            // 对每个桶里的元素分别进行排序
            // 偷懒，这里我写了冒泡排序
            for (int m = 1; m <= bucket[i][0]; m++) {
                for (int n = m + 1; n <= bucket[i][0]; n++) {
                    if (bucket[i][m] > bucket[i][n]) {
                        int t = bucket[i][m];
                        bucket[i][m] = bucket[i][n];
                        bucket[i][n] = t;
                    }
                }
            }
        }

        // 将结果搞回去
        for (int i = 0; i < toBeSorted.length;) {
            for (int m = 0; m < bucket.length; m++) {
                for (int n = 1; n <= bucket[m][0]; n++) {
                    toBeSorted[i++] = bucket[m][n];
                }
            }
        }

        // 输出结果
        for (int p = 0; p < toBeSorted.length; p++) {
            System.out.print(toBeSorted[p]);
        }
        System.out.println();
    }
}

from http://bubkoo.com/2014/01/15/sort-algorithm/bucket-sort/