读《啊哈！算法》——桶排序

小案例

一次考试中五个同学分别考了5分、3分、5分、2分、8分（10分满分），请按照从大到小的顺序排序。

提示的思路

1、要排序的5个数是在0-10之间的；
2、把分数从0-10当做数组的索引声明一个数组，初始化值为0；
3、要排序的5个数，依次放到对应的桶里，出现一次，对应的桶的值＋1；最终桶值为0的表示没有出现该分数；
4、输出桶值不为0的对应索引，值为几就打印几次；

Paste_Image.png

我的代码

<script>
    window.onload=function(){
        //1、要排序的5个数是在0-10之间的；
        var scoreArray = [5,3,5,2,8];
        //2、把分数从0-10当做数组的索引声明一个数组，初始化值为0；
        var sortArray =[];
        for(var i=0;i<11;i++){
            sortArray[i]=0
        }
        //3、要排序的5个数，依次放到对应的桶里，出现一次，对应的桶的值＋1；
        for(var i=0;i<scoreArray.length;i++){
            var index = scoreArray[i];
            sortArray[index] ++;
        }
        //4、输出桶值不为0的对应索引，值为几就打印几次；
        for(var i=sortArray.length-1;i>=0;i--){
            if(sortArray[i]!=0){
                for(var j=0;j<sortArray[i];j++){
                    console.log(i);
                }
            }
        }
    }
</script>

案例升级

输入n个0-1000之间的整数，并把它们从大到小排序。

function BucketSort(n){
    var buketArray =[];
    for(var i=0;i<=1000;i++){
        buketArray[i]=0;
    }
    for(var i=0;i<n;i++){
        var value = prompt('请输入0-1000之间的整数');
        buketArray[value] ++;
    }
    var  sortArray=[];
    for(var i=1000;i>=0;i--){
        if(buketArray[i]!=0){
            for(var j=0;j<buketArray[i];j++){
                sortArray.push(i);
            }
        }
    }
    return sortArray;
}

反思

for循环用的多，注意代码优化。例如在循环输入n个数的同时就可以为对应的桶值+1，不必设两个for循环。