用Javascript学算法之简单的桶排序

初学算法，把学到的东西用自己的语言和Javascript去做一遍。

举个栗子，河边有5个猴子去摘桃子，每个猴子摘的不一样多最多摘10个，A猴子摘了4个，B猴子摘了6个，C猴子摘了8个，D猴子摘了5个吃了3个还剩2个，E猴子傻，摘一个扔一个，最后只摘了2个。根据猴子最后的桃子数进行排序。 我们把他们摘得桃子数组成一个数组 [4,6,8,2,2]，我们用一种方法进行排序。

这么五个数还用算法了？用脑子想一下就行了 8最大放前面 6第二 4第三 后面是 2 2，最后是[8,6,4,2,2]。

好吧，如果有100个咋办= =~

所以言归正传，不是用脑子排序，是用能够用编程语言实现的算法排序。

下面执行我的排序过程了

1、在河边放11个水桶，分别贴上号码（0-10）

2、让猴子坐到自己摘到的桃子数对应编号的水桶里。

3、我们从最后一个水桶往前数，如果水桶里有猴子，那么我们把水桶号写在纸上，有几只猴子就写几次号码，比如，9号水桶里有1只猴子，8号水桶里有两只猴子，那么我们在纸上呈现的是 9 8 8。当然，猴子所在水桶的顺序也是猴子的排名。

4、我们写下的结果就是从大到小的排序，对应的猴子也是他们的排名

接下来我用Javascript进行编写程序

var arr = [4,6,8,2,2]

// 首先我们要11个水桶

var buket = new Array(11);
for (var i = 0; i <= 10; i ++) {
    buket[i] = 0;
}

// 然后，猴子有几个桃子就坐进对应编号的桶里

arr.forEach(function (x) {
    buket[x] ++;
});


// 然后就是从后往前 查水桶喽~

var newArr = [];

for (var i = 10; i >=0; i--) {
    for (var j = 0; j < buket[i]; j ++) {
        newArr.push(i);
    }
}

// 输出我们的排序结果
console.log(newArr);

好了 newArr 是不是就是我们排序的结果啦？

版权声明

本博客文章均为 范明非 原创或翻译，采用知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
原文地址： https://fanmingfei.com/posts/Bucket_Sort.html