gpt4 book ai didi

algorithm - 关于计数排序算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:32:15 25 4
gpt4 key购买 nike

我读过一个计数排序算法,它是这样的:

Counting Sort(A[1,..n]) //C[1,...k] is the temporary memory and k is the range of integers
for i<-- 1 to k
C[i]<-- 0
for j<-- 1 to n
C[A[j]]<--C[A[j]]+1
for i<--2 to k
C[i]<--C[i]+C[i-1]
for j<--n downto 1
B[C[A[j]]]<--A[j]
C[A[j]]<--C[A[j]]-1

我想知道如果我将最后一个更改为:for j<--1 to n ,算法也会正确吗???(有什么办法可以证明这个“for”算法是正确的???)

这样算法也稳定吗?

谢谢

最佳答案

该算法在两个方面都是正确的。它也很稳定,因为您现在拥有它。

如果你改变最后一个for按照你说的,它会停止稳定。

基本上,C[i] = how many elements <= i exist第三场结束后for环形。所以C[A[j]]为您提供值为 A[j] 的元素的最后位置按排序顺序,C[A[j]] - 1值为 A[j] 的元素的倒数第二个位置等等。这就是为什么要减少 C 中的值的原因.

因此,如果您关心稳定性,则必须开始以相反的顺序迭代原始数组:以便最后一个值为 x 的元素。在您的原始数组中首先放在新数组中。反向迭代原始数组将保证 x放在之后所有其他等于 x 的值,从而使算法稳定。

关于algorithm - 关于计数排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3076037/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com