排序算法-计数排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了排序算法-计数排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1273字，纯文字阅读大概需要2分钟。

内容图文

计数排序（升序为例）

思路：主要思想是统计每个整数在序列中出现的次数，进而推出每个数在序列中的位置
1. 找出序列中最大最小值，最小值 min， 最大值 max
2. 新建一个counts数组，范围是 [0, max - min], 先存储每个元素出现的次数，然后遍历该数组，使用每个位置存储的值是当前元素的个数+前面元素的总和
3. 遍历counts数组，取出元素赋值回array

class CountSort {
    
    var array = [5, 7, 2, 8, 9, 4, 7, 3, 2]
    var counts: [Int]!
    
    func sort() {
        // 遍历找出序列最大最小值
        var max = array[0]
        var min = array[0]
        for i in 1 ..< array.count {
            if max < array[i] {
                max = array[i]
            }
            
            if min > array[i] {
                min = array[i]
            }
        }
        // 统计元素出现的次数
        counts = Array<Int>(repeating: 0, count: max - min + 1)
        for i in 0 ..< array.count {
            counts[array[i] - min] += 1
        }
        // counts元素中后一个元素的值是前面元素总和+当前元素的数量
        // 这样每个索引对应的元素就是排序后的位置
        for i in 1 ..< counts.count {
            counts[i] += counts[i - 1]
        }
        // 新建数组存储排序好的数
        var results = Array<Int>(repeating: 0, count: array.count)
        for i in (0 ..< array.count).reversed() {
            // 取出array元素在counts序列中的位置
            let countIndex = array[i] - min
            counts[countIndex] -= 1
            results[counts[countIndex]] = array[i]
        }
        // 覆盖array
        for i in 0 ..< results.count {
            array[i] = results[i]
        }
    }
}

* 最好、最坏、平均时间复杂度：O(n + k)，k是最大最小值范围

* 空间复杂度： O(n + k)

* 稳定性： 稳定

内容总结

以上是互联网集市为您收集整理的排序算法-计数排序全部内容，希望文章能够帮你解决排序算法-计数排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---