首页 > 后端开发 > Golang > 正文

计数排序

WBOY
发布: 2024-07-21 07:24:49
原创
1210 人浏览过

Counting Sort

这是用于整数数组或以整数为键的结构的排序算法。当整数范围与输入大小相同时特别有用。

主要思想是确定整数出现的频率,并用它来确定排序顺序。

示例:假设我们得到数组 {1,3,1,2}。

首先确定此输入的整数范围,最大值和最小值,1 和 3。

接下来创建一个数组,将其称为 counts 数组,即整数范围的大小+1,因此在本例中为 3 (3-1+1)。
迭代输入数组,增加相应条目的计数。给定输入值的计数将放置在 counts[value - min] 处。对于给定的输入,counts[0] 将保存值 1 的计数。

这会产生计数数组:{2,1,1}

现在确定累计计数,本质上是 counts[i] = counts[i-1]+counts[i]。

这会产生累积计数数组:{2,3,4}

为排序后的输入创建输出数组。

现在,以相反的顺序迭代输入。

在每一步中,检索输入数组中值的累积计数。该值将被放置在与检索到的计数 - 1 相对应的输出数组索引处。然后递减累积计数值。

在第一步中,检索值 2 且累积计数为 3。该值应放置在输出中的索引 2 (3-1) 处。

下一次迭代时,值1,累计计数2;所以这个“1”被放置在输出的索引 1 (2-1) 处。

继续,数值3,累计次数4;将其放置在输出的索引 3 处。

最后,第二次值为1,累计计数为1(因为第一次看到计数就递减了);所以这个“1”被放置在输出的索引 0 处。

,了解反向迭代如何保留相等元素的顺序,从而使排序“稳定”

排序后的数组为 {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}
登录后复制

可以提高效率吗?在下面留下您的意见和建议。

谢谢!

这篇文章以及本系列所有文章的代码可以在这里找到

以上是计数排序的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板