排序(计数,基数,桶)

对数据有要求,但时间复杂度为O(n)

桶排序(BucketSort)

桶排序实际上是一种思想,主要用于排序 大批量数据(10GB),
进行外部排序(数据储存在外部磁盘中),
进行分批次排序

先扫描一遍文件,确定数据范围,如1-100
首先,划分每个’桶’内存放的数据区间,如1-10,11-20…91-100
然后,扫描数据将数据存放在属于自己范围内的桶内
再次,依次对各个桶进行排序
最后,按顺序 直接拼接 各桶数据.

数据量大可继续分桶,数据不均匀可桶内再分桶

/** 找到数据范围,确定每个桶范围,创建桶,数据分桶,对每个桶调用排序 */

// 桶排序
function bucketSort(array, bucketSize = 5) {
    if (array.length < 2) {
        return array
    }
    const buckets = createBuckets(array, bucketSize)
    // 5.对每个桶调用排序
    return sortBuckets(buckets)
}

function createBuckets(array, bucketSize) {
    let minValue = array[0]
    let maxValue = array[0]
    // 1.找到数据范围:遍历数组，找到数组最小值与数组最大值
    for (let i = 1; i < array.length; i++) {
        if (array[i] < minValue) {
            minValue = array[i]
        } else if (array[i] > maxValue) {
            maxValue = array[i]
        }
    }
    // 2.确定每个桶范围:根据最小值、最大值、桶的大小，计算得到桶的个数
    const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
    // 3.创建桶:建立一个二维数组，将桶放入buckets中
    const buckets = []
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = []
    }
    // 4.数据分桶:计算每一个值应该放在哪一个桶中
    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
        // i左边是已排完序的,i右边是待排序区
        // array[i] 在i的左边区域内,从右往左对比,
        // 比 array[i] 大的都右移,碰到比array[i]小的数时停止,
        while (j >= 0) {
            if (array[j] > value) {
                array[j + 1] = array[j] // 移动
                j--
            } else {
                break
            }
        }
        //  array[i]插入到碰见的第一个比自己小的数右边,
        //  此时j+1右边也会都是 比自己大的数
        array[j + 1] = value // 插入数据
    }
}

计数排序(CountingSort)

计数排序 其实是 桶排序 的一种特殊情况
50万考生 分数0-900 分为901个桶 同一个桶内分数相同
只需将考生 依次输出到一个数组中 就实现了排序.

假设 a = [2,5,3,0,2,3,0,3] 八个考生的分数 数组进行排序

创建c1 = [2,0,2,3,0,1] 下标对应分数,数值对应 等于 分数的考生个数

创建c2 = [2,2,4,7,7,8] 由c1变种而来,数值对应 小于等于 分数的考生个数

创建r = [] 8位空数组,存放排序完的数据

从后 往前扫描a,得到3,从c2[3]得到7,

代表3位于r第7位(r[6]),因为c2[3]表示 小于等于 3分的有7个

于是r[6] = 3,3排序结束,

此时小于等于3的元素只剩6个,c2[3] = c2[3]-1

继续 往前扫描a,得到0,由c2[0]知小于等于0的只有2个

于是0位于r第二位,r[1] = 2,c2[0] = c2[0]-1 = 1,

继续 往前扫描a,以此类推

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
}

计数排序 只能用在 数据范围不大 的场景中,只能给 非负整数 排序.

如果 数据范围k 大于 要排序的数据数n,则不适用
如果 存在非负整数,则需在 不改变相对大小 的情况下先转换为 非负整数

基数排序(RadixSort)

10万个手机号码从小到大排序

使用快速排序 时间复杂度O(nlogn),使用桶排序,计数排序 则11位范围太大

此时应使用 基数排序

基数排序,将数据 按从低位到高位 依次进行O(n)的稳定排序,进行K次(K为数据位数)

基数排序 对数据的要求:

需要可以分割出独立的“位”来比较,
位之间有递进的关系(如果a数据的高位比b数据大,那剩下的低位就不用比较了),
每一位的数据范围不能太大,要可以用线性排序算法来排序
(否则,基数排序的时间复杂度就无法做到 O(n) 了。)

C语言的qsort函数策略

优先使用 归并排序 ,(归并排序应用与小数据量数据 如1kb 2kb)
数据量较大时(100MB),改用 快速排序,
快速排序过程中 区间元素个数小于4时, 使用插入排序,不继续使用递归快速排序