数组-计数排序

采用计数排序方式对数组进行排序

计数排序百科:计数排序(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]

参考:

• 计数排序百科
• 一像素

考察要点:

• 数组
• 排序