计数排序
算法步骤
计数排序的算法步骤如下:
找出待排序的数组中最大和最小的元素。
统计数组中每个值为 i 的元素出现的次数,存入新数组 C 的第 i 项。
对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加)。
反向填充目标数组 B:将每个元素 i 放在新数组 B 中的第 C(i) 项,每放一个元素就将 C(i) 减去 1。
示例代码
数组
[5, 3, 8, 2, 1, 4]
中最小值为 1,最大值为 8。创建一个长度为
max - min + 1
的计数数组countArr
,此时countArr
的初始状态为[0, 0, 0, 0, 0, 0, 0, 0]
。统计每个元素出现的次数,遍历原始数组,将每个元素减去最小值作为索引,并将对应位置的计数加一。统计结束后,
countArr
的状态为[1, 1, 1, 1, 1, 0, 0, 1]
。累加计数数组,从第二个元素开始,每个元素的值等于前一个元素值加当前元素值。累加结束后,
countArr
的状态为[1, 2, 3, 4, 5, 5, 5, 6]
。创建一个新数组
sortedArr
,长度与原始数组相同。反向遍历原始数组,将每个元素在
countArr
中的值减一作为索引,并将对应位置的元素放入sortedArr
。同时,将对应位置的计数减一。最终得到排序后的数组sortedArr
。