美文网首页数据结构和算法分析
桶排序、计数排序、基数排序算法

桶排序、计数排序、基数排序算法

作者: 云飞扬1 | 来源:发表于2020-02-24 14:10 被阅读0次

这3种排序通常都算作是一类排序算法,他们不像选择、冒泡、归并、快排之类的是基于比较来排序的。

1. 桶排序

以一个例子来说明:有一个数组为 [3, 4, 4, 7, 9, 1, 8, 1],我们能找到其中最小值为 min = 1,其中最大值为 max = 9,如果每个桶只装 2 种不同的数据(同种数据可以有多个),那么需要定义 (max - min) / 2 + 1 = 5 个桶,这5个桶按顺序只能装这样子的数据:[1, 2]、[3, 4]、 [5, 6]、 [7, 8]、 [9]。也就是说第 1 个桶只装 1 和 2,第 2 个桶只装 3 和 4,依次类推。遍历一遍数组,将数据分别装入到对应的桶中,这5个桶内的实际数据应该为:[1, 1]、[3, 4, 4]、[ ]、[7, 8]、[9],第 3 个桶是空桶。接着我们对每个桶排序,排好序之后,这 5 个桶按顺序合起来就是排好序的数据了。

代码如下(kotlin编写):

/**
 * @param array 待排序数组
 * @param bucketSize 桶的个数
 */
private fun bucketSort(array: Array<Int>, bucketSize: Int) {
    if (array.size <= 1 || bucketSize < 1)
        return
    //找出最大值、最小值
    var min = array[0]
    var max = array[0]
    for (item in array) {
        if (item > max) {
            max = item
        } else if (item < min) {
            min = item
        }
    }

    //定义桶
    var bucketList = ArrayList<ArrayList<Int>>(bucketSize)
    for (i in 0 until bucketSize) {
        bucketList.add(ArrayList())
    }

    //每个桶数字的间隔区间
    var section = (max - min + 1) / bucketSize
    if (section == 0)
        section = 1
    //遍历数据,放到对应桶中
    for (i in array.indices) {
        var bucketIndex = (array[i] - min) / section
        if (bucketIndex >= bucketList.size)
            bucketIndex = bucketList.size - 1
        var list = bucketList[bucketIndex]
        list.add(array[i])
    }

    for (i in bucketList.indices) {
        val itemList = bucketList[i]
        if (itemList.size <= 1)
            continue
        var arr: Array<Int> = itemList.toTypedArray()
        //数据少的话,直接使用插入排序,也可选择其他如快排,不会有太大区别
        insertSort(arr)
        itemList.clear()
        for (item in arr) {
            itemList.add(item)
        }
    }
    var i = 0
    for (itemList in bucketList) {
        for (item in itemList) {
            array[i++] = item
        }
    }
}

桶排序有很多局限性,它一般应用在特殊的场合下,桶大小的分配会影响到排序的性能。
桶排序是否稳定,要看桶内部的排序用什么算法。
其空间复杂度为:其时间复杂度与桶的个数有关,桶越多的情况下,其时间复杂度接近 O(n)

2. 计数排序

计数排序有 2 个基本条件:

  1. 计数排序不能有负数,如果有负数,可以统一加上一个正数之后,将所有数都转换为大于等于 0 的数,排好序之后再减去之前加的正数;
  2. 计数排序里的最大数不宜过大,否则会比较浪费空间;
计数排序过程图.png

具体逻辑,还是看代码比较清楚:

/**
 * 计数排序,待排序数组不能有负整数,如果有则需要将数据处理成非负整数
 */
fun countingSort(array: IntArray?) {
    array ?: return
    if (array.size <= 1)
        return
    //查找最大值
    var max = array[0]
    for (item in array) {
        if (max < item) max = item
    }

    //定义计数数组 [0, max],大小为 max + 1,
    var countingArr = Array(max + 1) { 0 }
    //遍历数组,统计每个数字的个数,例如数字 1 的个数存储在 countingArr[1] 中
    //统计结束之后,countingArr[i] 表示数字 i 在数组中的个数
    for (item in array) {
        countingArr[item]++
    }

    //计数数组依次累加,累加后对计数数组来说, countingArr[i] 存储的是 <= i 的数据的个数
    //其实这是构造一个前缀和数组
    for (i in 0 until countingArr.size - 1) {
        countingArr[i + 1] = countingArr[i + 1] + countingArr[i]
    }

    //申请一个临时数组,大小与待排序数组一样大
    var tmpArr = Array(array.size) { 0 }
    //将每个元素 num 放在新数组的第 countingArr[num] 项,每放一个元素就将 countingArr[num] 减去1。
    //假设countingArr[num] = c, 则表示原数组中 <= num 的元素个数有 c 个,我们想象一下如果将原数组排好序之后
    //则排好序的数组中索引为 c-1 的数肯定为 num
    for (num in array) {
        tmpArr[countingArr[num] - 1] = num
        countingArr[num]--
    }

    //从排好序的数组拷贝数据到原数组里
    for (i in tmpArr.indices) {
        array[i] = tmpArr[i]
    }
}

计数排序是稳定的
空间复杂度:O(n + k),k 为最大数的值
时间复杂度:O(n + k),k 为最大数的值,当 k 比较小时,其复杂度接近于 O(n)

3. 基数排序

通过数据的“位”来进行排序,可以从低位到高位进行排序,也可行从高位到低位进行排序,所有“位”都比较完毕之后,也就排好序了。如果“位”不足,可以补 0 或者其他。举个例子:
待排序数据列:178、50、34、1、8、251
比较个位:50、1、251、34、178、8
比较十位:1、8、34、50、251、178
比较百位:1、8、34、50、178、251
最后排序完成,代码如下:

/**
 * 基数排序
 */
fun radixSort(array: IntArray?) {
    array ?: return
    if (array.size <= 1)
        return
    //查找最大值
    var max = array[0]
    for (item in array) {
        if (max < item) max = item
    }
    //计算最大值的位数,例如 max = 148,则位数为 3
    var maxDigit = 0
    while (max != 0) {
        maxDigit++
        max /= 10
    }

    //每位的数字范围是[0-9],所以桶的大小设置成 10
    val bucketList = ArrayList<ArrayList<Int>>(10)
    for (i in 0 until 10) {
        bucketList.add(ArrayList())
    }

    //从低位到高位开始排序,这里采用桶排序
    var mod = 10
    var divide = 1
    //每位都进行一次桶排序
    for (i in 0 until maxDigit) {
        //遍历数据,根据"位"来判断数据放在哪个桶中
        for (j in array.indices) {
            val item = array[j]
            //取出数字的"位",例如 158 的个位为:(158 % 10) / 1 = 8
            //158 的十位为:(158 % 100) / 10 = 5
            //158 的百位为:(158 % 1000) / 100 = 1
            val num = (item % mod) / divide
            bucketList[num].add(item)
        }

        //从桶中取出数据放在原数组中,同一个桶中存储的是“位”相同的数据
        var index = 0
        for (list in bucketList) {
            for (item in list) {
                array[index++] = item
            }
            list.clear()
        }

        mod *= 10
        divide *= 10
    }
}

基数排序也是稳定的排序方式
空间复杂度:O(n)
时间复杂度:O(k * n),当 k 不大时,其复杂度接近于 O(n)

相关文章

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • php-计数排序、基数排序、桶排序

    计数排序、基数排序、桶排序 时间复杂度 O(n) 计数排序 基数排序 桶排序

  • 排序算法三(桶,计数,基数)

    桶排序,计数排序,基数排序算法的时间复杂度都是线性的,所以把这类排序算法叫作线性排序。 桶排序 概念:将要排序的数...

  • 算法入门——计数排序、桶排序、基数排序

    上篇文章我们学习了算法入门——归并排序、希尔排序,这篇文章我们学习算法入门——计数排序、桶排序、基数排序。 计数排...

  • 排序算法概述

    十大排序算法:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序、希尔排序、计数排序,基数排序,桶排序 算法...

  • 线性排序

    一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排...

  • 桶排序、计数排序、基数排序

    一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排...

  • 数据结构与算法——计数排序、桶排序、基数排序

    数据结构与算法——计数排序、桶排序、基数排序 计数排序 计数排序有如下四个步骤。 首先会对每个输入进行频率统计,得...

  • 11|线性排序:如何根据年龄给100万用户数据排序?

    一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法的时间复杂度为O(n)。3....

网友评论

    本文标题:桶排序、计数排序、基数排序算法

    本文链接:https://www.haomeiwen.com/subject/pnosqhtx.html