黑马程序员技术交流社区

标题: 【上海校区】Java实现桶排序 [打印本页]

---

作者: 不二晨    时间: 2019-1-7 09:42
标题: 【上海校区】Java实现桶排序
桶排序：使用额外空间，以空间换时间思想，，因此时间复杂度为O(n+m)

1.1  基本思想

桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的范围后，准备和这个范围同样数量的桶，并将元素放在对应的桶中，如待排元素为｛3,1,5,9,6,5,0｝，就要准备10个桶标号为0到9（代码中对应一个数组的下标），将每个元素放入对应桶中，再将所有元素按顺序输出（代码中则按顺序将数组i下标输出arrary次），即为{0,1,3,5,5,6,9}。





public class TestBucketSort {
        private int[] bucket;
        private int[] array;

        // size是一个范围
        public TestBucketSort(int[] array) {
                this.array = array;
                int max = array[0];
                int min = array[0];
                for(int i=0; i<array.length; ++i){
                        if(array>max){
                                max = array;
                        }
                        if(array<min){
                                min = array;
                        }
                }
                bucket = new int[max-min+1]; //算出需要开辟多少个空间
               
        }

        public void sort() {
                for (int i = 0; i < array.length; ++i) {
                        bucket[array]++;
                }
        }

        // 遍历桶，并得到每个桶中数n，并输出n次该桶下标
        public void print() {
                for (int i = 0; i < bucket.length; i++){
                        for (int j = 0; j < bucket; j++){
                                System.out.println(i);
                        }
                }       
        }
       
        public static void main(String[] args) {
                 int[] array = new int[]{3,1,5,9,6,5,0};
       TestBucketSort order = new TestBucketSort(array);
       order.sort();
       order.print();
        }
}

---------------------
转载，仅作分享，侵删
作者：qq1010234991
原文：https://blog.csdn.net/qq1010234991/article/details/83082419

---

作者: 不二晨    时间: 2019-1-10 10:26
奈斯，加油

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2