SortAlgosKt(6) - 计数排序

鸽了几天，但是 better late than never ，俺又回来了，妹想到吧。追 SPN 追到了最新的一集，很喜欢 Castiel 最后说的一句话：

Happiness isn’t in the having.It’s in just being.It’s in just saying it.

算法思想

前面几篇讲的所有排序算法都是比较算法（在排序的最终结果中，各元素的次序依赖于它们之间的比较）。而计数排序是非比较排序，它的核心思想就是统计序列中每一种元素出现的次数，由此计算出对于每一个元素，有多少个元素比当前元素小，即可得到当前元素应该排序后应该放置的位置。具体的实现流程可以看下面的代码注释。

算法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fun countingSort(nums: IntArray): IntArray {
    if (nums.size < 2) return nums
    //获得数组最大值
    var max = Int.MIN_VALUE
    for (num in nums) {
        max = Math.max(num, max)
    }
    //分别统计(0..max)在数组中出现的次数
    val arr = IntArray(max + 1)
    for (num in nums) {
        arr[num] += 1
    }
    //通过累加，计算对于每一个元素，数组中有多少个元素是小于或者等于该元素的
    for (i in 1..arr.lastIndex) {
        arr[i] += arr[i - 1]
    }
    val ans = IntArray(nums.size)
    //倒序遍历数组，根据上面得到的arr，把每个元素放到相应的位置
    for (i in nums.lastIndex downTo 0) {
        ans[arr[nums[i]] - 1] = nums[i]
        arr[nums[i]] -= 1
    }
    return ans
}

文章目录

算法思想

算法实现