【广州校区】【原创】快速排序算法-桶排序介绍 - 黑马程序员技术交流社区

设待排序序列的元素取值范围为0到m，则我们新建一个大小为m+1的临时数组并把初始值都设为0，遍历待排序序列，把待排序序列中元素的值作为临时数组的下标，找出临时数组中对应该下标的元素使之+1；然后遍历临时数组，把临时数组中元素大于0的下标作为值按次序依次填入待排序数组，元素的值作为重复填入该下标的次数，遍历完成则排序结束序列有序。

假设有11个桶，编号从0~10。每出现一个数，就将对应编号的桶中的放一个小旗子，最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次。

[Java] 纯文本查看 复制代码

public class SortTest {

        /**

         * 桶排序，此处从小到大排序。

         * 如果需要从到到小，只需逆向遍历桶索引

         * @param data

         * @param max

         */

        public static void buktSort(int[] data,int max){

                //创建并初始化桶的值

                int[] buket = new int[max];

                for(int i=0; i<max;i++){

                        buket=0;

                }

                

                //将要排序的元素当做桶的索引，找到对应的桶位置，进行计数，

                //即桶的索引为要排序的值，索引对应的位置的值为出现 的次数

                for(int i =0; i<data.length; i++){

                        buket[ data ]++;

                }

                

                //因为桶索引即为要排序的元素，而且索引本身就是从小到大排序的，

                //所以从小到大输出桶索引，为0的不输出，大于1的按出现的次数依次输出,即能完成排序

                for(int i=0; i<buket.length; i++){

                        for(int j=0; j<buket; j++){

                                System.out.print(i + ",");

                        }

                }

        }

        

        //桶排序测试

        public static void main(String[] args) {

                int[] data = {1,0,10,3,5,6,6,8};

                SortTest.buktSort(data, 11);

        }

}