美文网首页力扣精解
数组-计数排序

数组-计数排序

作者: coenen | 来源:发表于2021-08-13 07:33 被阅读0次
采用计数排序方式对数组进行排序

计数排序百科:计数排序(Counting Sort),计数排序是一个非基于比较的排序算法,它的优势在于对一定范围内的整数排序时,它的复杂度是O(n+k)(其中k是整数的范围),快于任何比较排序算法.采用空间换时间的做法,而且当O(k) > O(n*log(n))的时候其效率反而不如基于比较的排序.基于比较排序的时间复杂度在理论下限是O(n*log(n)).

摘一个示例做个说明.
示例 1:
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]
算法思想:

计数排序对输入的数据有附加的限制条件:

  1. 输入的线性表的元素属于有限偏序集S
  2. 设输入的线性表的长度为n, |S| = k(表示集合中S中元素的总数目为k),则k = O(n).

在这两个条件下,计数排序的复杂性为O(n).
计数排序的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定).一旦有了这个信息,就可以将x直接存放刀最终的输出序列的正确位置上.

算法原理:

假设输入的线性表L的长度为n,L=L1,L2,..,Ln,线性表的元素属于有限偏序集S,|S| = k, 且k=O(n),S={S1,S2,..Sk},则排序可以描述如下

  1. 扫描整个集合S,对每一个,对每一个Si∈S,找到在线性表L中小于等于Si的元素的个数T(Si)
  2. 扫描整个线性表L,对L中的每一个元素Li,将Li放在输出线性表的第T(Li)个位置上,并将T(Li)减1.
  3. 算法演示 计数排序演示.gif
算法分析:
  1. 时间复杂度
    计数排序最好、最坏、平均时间复杂度均为O(n+k).
  2. 空间复杂度
    计数排序空间复杂度为O(n+k).
  3. 算法稳定性
    计数排序是一种稳定排序算法.

代码实现-Swift版本:

func countingSort(_ num: [Int]) -> [Int]{
    // 数组最大最小元素
    let maxNum: Int = num.max()!
    let minNum: Int = num.min()!
    // 初始化数组空间为原数组大小
    var result: [Int] = [Int](repeating: 0, count: num.count)
    
    // 计算k值,
    let k: Int = maxNum - minNum + 1
    // 初始化k大小空间的数组,做临时数据存储
    var tmp: [Int] = [Int](repeating: 0, count: k)
    
    // 统计数组中每个值为元素出现的次数,存入数组的相应位置
    for i in 0 ..< num.count {
        tmp[num[i] - minNum] += 1
    }
    
    // 对所有的计数累加,(相邻数据相加)
    for i in 1 ..< tmp.count {
        tmp[i] += tmp[i - 1]
    }
    
    // 反向填充目标数组
    for i in (0 ..< num.count).reversed() {
        // 按存取的方式取出c的元素
        tmp[num[i] - minNum] -= 1
        result[tmp[num[i] - minNum]] = num[i]
    }
    
    return result
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

考察要点:

  • 数组
  • 排序

相关文章

  • 数组-计数排序

    采用计数排序方式对数组进行排序 计数排序百科:计数排序(Counting Sort),计数排序是一个非基于比较的排...

  • 算法:计数排序

    计数排序 计数排序,针对数据重复度比较高的数组。将数据转化为数组下标存储在新的统计数组中,然后依次遍历原数组,统计...

  • NumPy API(十)——输入和输出排序、搜索和计数

    排序、搜索和计数 排序 sort(a[, axis, kind, order]) 返回数组的排序副本。 lexso...

  • C语言十大排序一

    计数排序 注意点和使用场景计数排序只能用于有限数据的排序,并且数字不是非常大的时候 计数排序的条件1.数组索引必须...

  • 常用排序算法总结9一一计数排序

    定义 计数排序(英语:Counting Sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C,其中...

  • 计数排序与计数排序的优化

    一.计数排序 算法原理 1.找出待排序的数组中最大和最小的元素2.统计数组中每个值为i的元素出现的次数,存入数组c...

  • 排序算法⑧——计数排序

    计数排序 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排...

  • 排序算法

    计数排序 思想: 利用数组的索引,将对应的数组当做数组的索引,将所对应的元素赋给一个值,遍历这个数组取值 选择排序...

  • 06-C语言基本排序算法

    计数排序(Counting Sort) 排序思路1.找出待排序数组的最大值2.定义一个索引最大值为待排序数组最大值...

  • 计数排序

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入...

网友评论

    本文标题:数组-计数排序

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