// 待排序的数组
var arr = [8, 5,5,3,2]
// 排序后的数组
var arr2 = []
// 桶容器，它的容量是由待排序数组中的最大值＋１决定的
var book = new Array(Math.max.apply(null, arr) + 1);

//　初始化桶(m)
for (var i = 0; i < book.length; i++) {
    book[i] = 0
}

// 往桶中插入flag(n)
arr.forEach(function (e, i) {
    book[e]++
})

// 循环桶并且查看flag。打印出桶的当前索引并且放入arr2中(m)
book.forEach(function (e, index) {
    // 循环桶的flag数量，并且将当前桶的索引放入数组中（n）
    for (var i = 0; i < +e; i++) {
        arr2.push(index)
    }
})

//　输出排序后的数组
console.log(arr2)

/*
该排序方法名为：简易桶排序
时间复杂度的计算公式：
O(m+n+m+n) = O(2*(m+m))
时间复杂度可以忽略较小的常熟
O(m+n)
通常大写更有逼格 
O（M+N）
*/

// 待排序的数组
var arr = [8, 5,5,3,2]

// 最外部的循环其实没什么参与什么作为。
// 至于为什么要-1 其实很容易理解。因为最后一次的时候是不需要与自己比较的。所以绕过了
// 当然你减不减好像也没什么区别。只是减少次数来优化罢了
for (var i = 0;i < arr.length - 1; i++) {
    // 重点想清楚这里为什么要-i。其实也很简单，每一次轮回，都会把最大（小）数塞到最后。
    // 所以下次就不必去比较最后一位了。同理，你减不减都无所谓。只是优化而已。但这个优化的幅度比较大
    for (var j = 0; j < arr.length - i; j++) {
        // 这里的比大小判断决定排序是倒序还是正序
        if (arr[j] > arr[j+1]) {
            // 以下代码只是普通的交换变量逻辑。没什么好说的。
            // 如果真要说的话，只能说无论临时变量存储的是j的值还是j + 1的值都是可以的
            var temp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = temp
        }
    }
}

console.log(arr)

/*
该排序法名为：冒泡排序法
思路而言几乎没有难点，人人都能理解。但真要动手写的时候，却总有写不出或者想不出的情况。
原因就在于没有多写，写完也要看看套路。
双重循环，以及那些可有可无的-1 和 -i
以及注意外层的循环没有参与计算的作为。只有内存的j循环进行了比较或交换而已
*/