阅读 13

排序算法笔记之计数排序

###计数排序

  • 计数排序的概念
    1. 计数排序是非比较排序
    2. 是利用空间换时间的排序算法
    3. 适合对一定范围内的整数进行排序
    4. 统计每个整数在序列中出现的次数,进而推算出在有序序列中的索引

例: array:[7,3,5,8,6,7,4,5]

阿斯顿.png

  • 计数排序的流程(参考上图)
    • 假设array中的最小元素值是min
    • 元素k对应的counts的索引就是k-min
    • k在排好序的有序序列中索引为counts[k - min] - p
      • p代表倒数第p个k
      • 如元素8的索引是 counts[8 - 3] - 1 == 8
      • 倒数第2个7是counts[7 - 3] - 2 == 5
    • 寻找元素在有序序列中的索引并放入有序序列后,次数-1

最终排序结果[3,4,5,5,6,7,7,8]

// 遍历数组找到最大最小值
        for i in 0..<array.count {
            if array[i] > max {
                max = array[i]
            }
            if array[i] < min {
                min = array[i]
            }
        }
        
        var counts = Array(repeating: 0, count: max - min + 1)
        
        // 遍历array中的数组 放到counts索引位置
        for i in 0..<array.count {
            counts[array[i] - min] += 1
        }
        
        /// 将counts数组的值累加前一索引的值
        for i in 1..<counts.count {
            counts[i] += counts[i - 1]
        }
        
        var newArray = Array(repeating: 0, count: array.count)
        
        for i in (0..<array.count).reversed() {
            counts[array[i] - min] -= 1
            newArray[counts[array[i] - min]] = array[i]
        }
复制代码
  • 计数排序的稳定性

    • 计数排序属于稳定的排序
  • 计数排序的时间复杂度和空间复杂度

    • 时间复杂度 时间复杂度为O(n + k)
    • 空间复杂度
      • O(n + k)
    • k是整数的取值范围

源码及单元测试:https://github.com/yukifeng/suanfaStudy