vlambda博客
学习文章列表

线性排序:桶排序、计数排序

一、桶排序

桶排序的核心思想就是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序(插入或快排),桶内的排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
线性排序:桶排序、计数排序
我们用代码来实现:
// 思路:
// 将数组中的数据,按桶进行划分,将相邻的数据划分在同一个桶中
// 每个桶用插入排序算法(或者快速排序)进行排序
// 最后整合每个桶中的数据

function bucketSort(array, bucketSize = 5) {
    if (array.length < 2) {
        return array
    }
    const buckets = createBuckets(array, bucketSize)
    return sortBuckets(buckets)
}

function createBuckets(array, bucketSize) {
    let minValue = array[0]
    let maxValue = array[0]
    // 遍历数组,找到数组最小值与数组最大值
    for (let i = 1; i < array.length; i++) {
        if (array[i] < minValue) {
            minValue = array[i]
        } else if (array[i] > maxValue) {
            maxValue = array[i]
        }
    }
    // 根据最小值、最大值、桶的大小,计算得到桶的个数
    const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
    // 建立一个二维数组,将桶放入buckets中
    const buckets = []
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = []
    }
    // 计算每一个值应该放在哪一个桶中
    for (let i = 0; i < array.length; i++) {
        const bucketIndex = Math.floor((array[i] - minValue) / bucketSize)
        buckets[bucketIndex].push(array[i])
    }
    return buckets
}

function sortBuckets(buckets) {
    const sortedArray = []
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i])
            sortedArray.push(...buckets[i])
        }
    }
    return sortedArray
}

// 插入排序
function insertionSort(array) {
    const { length } = array
    if (length <= 1) return

    for (let i = 1; i < length; i++) {
        let value = array[i]
        let j = i - 1

        while (j >= 0) {
            if (array[j] > value) {
                array[j + 1] = array[j] // 移动
                j--
            } else {
                break
            }
        }
        array[j + 1] = value // 插入数据
    }
}
桶排序的时间复杂度是多少呢?
如果要排序的数据有 n 个,我们把它们均匀地划分到 m 个桶内,每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序,时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk),因为 k=n/m,所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时,log(n/m) 就是一个非常小的常量,这个时候桶排序的时间复杂度接近 O(n)。
桶排序注意事项:
桶排序对要排序数据的要求是非常苛刻的。
首先,要排序的数据需要很容易就能划分成 m 个桶,并且,桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。其次,数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后,有些桶里的数据非常多,有些非常少,很不平均,那桶内数据排序的时间复杂度就不是常量级了。在极端情况下,如果数据都被划分到一个桶里,那就退化为 O(nlogn) 的排序算法了。


二、计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据,所处的范围并不大的时候,比如最大值是 k,我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的,省掉了桶内排序的时间。
假设有 8 个考生,分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8]中,它们分别是:2,5,3,0,2,3,0,3。
考生的成绩从 0 到 5 分,我们使用大小为 6 的数组 C[6]表示桶,其中下标对应分数。不过,C[6]内存储的并不是考生,而是对应的考生个数。像我刚刚举的那个例子,我们只需要遍历一遍考生分数,就可以得到 C[6]的值。
从图中可以看出,分数为 3 分的考生有 3 个,小于 3 分的考生有 4 个,所以,成绩为 3 分的考生在排序之后的有序数组 R[8]中,会保存下标 4,5,6 的位置。
线性排序:桶排序、计数排序
我们对 C[6]数组顺序求和,C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数 k 的考生个数(如:c[2]对应的值是4,代表小于等于2分数的有四个人(得分为2、0、2、0的这四个人))。
我们从后到前依次扫描数组 A。比如,当扫描到 3 时,我们可以从数组 C 中取出下标为 3 的值 7,也就是说,到目前为止,包括自己在内,分数小于等于 3 的考生有 7 个,也就是说 3 是数组 R 中的第 7 个元素(也就是数组 R 中下标为 6 的位置)。当 3 放入到数组 R 中后,小于等于 3 的元素就只剩下了 6 个了,所以相应的 C[3]要减 1,变成 6。以此类推,当我们扫描到第 2 个分数为 3 的考生的时候,就会把它放入数组 R 中的第 6 个元素的位置(也就是下标为 5 的位置)。当我们扫描完整个数组 A 后,数组 R 内的数据就是按照分数从小到大有序排列的了。
代码如下:
const countingSort = array => {
    if (array.length <= 1) return

    const max = findMaxValue(array)
    const counts = new Array(max + 1)

    // 计算每个元素的个数,放入到counts桶中
    // counts下标是元素,值是元素个数
    array.forEach(element => {
        if (!counts[element]) {
            counts[element] = 0
        }
        counts[element]++
    })

    // counts下标是元素,值是元素个数
    // 例如:array: [6, 4, 3, 1], counts: [empty, 1, empty, 1, 1, empty, 1]
    // i是元素, count是元素个数
    let sortedIndex = 0
    counts.forEach((count, i) => {
        while (count > 0) {
            array[sortedIndex] = i
            sortedIndex++
            count--
        }
    })
    return array
}

function findMaxValue(array) {
    let max = array[0]
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i]
        }
    }
    return max
}

console.log(countingSort([7, 5, 1, 9, 2, 3, 6]))
计数排序只能用在数据范围不大的场景中,如果数据范围 k 比要排序的数据 n 大很多,就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。