/**
 * 基数排序，从数字的末位开始，对每一位进行一次“桶排序”
 */
fun radixSort(array: IntArray) {

    //先找出最大的数，计算最大的数有几位
    var maxValue = array[0]

    array.forEach {
        maxValue = max(maxValue, it)
    }

    var length = 1
    while ((maxValue / 10) != 0) {
        maxValue /= 10
        length++
    }

    var mod = 10
    var dev = 1

    for (i in 0 until length) {
        val buckets = Array(10) {
            MutableList(0) { 0 }
        }

        //每个元素入桶
        array.forEach {

            val whichBucket = (it % mod) / dev

            buckets[whichBucket].add(it)

        }

        //从桶中捞出来重新给到array
        var index = 0
        buckets.forEach {
            if (it.isNotEmpty()) {
                it.forEach { element ->
                    array[index++] = element
                }
            }
        }

        mod *= 10
        dev *= 10
    }
}