关于计数排序算法 [英] about counting sort algorithm

查看:25
本文介绍了关于计数排序算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

I have read a counting sort algorithm which is like this:

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 更改为:for j<--1 to n ,算法也会正确吗???(有没有办法证明使用这个for"算法将是正确的???)

I want to know that if I change the last for to this:for j<--1 to n ,the algorithm will be correct too???(is there any way to show that with this "for" the algorithm will be correct??? )

这样算法也稳定了吗?

谢谢

推荐答案

该算法双向正确.它也很稳定,因为您现在拥有它.

The algorithm is correct both ways. It is also stable as you have it right now.

如果你把最后一个 for 改成你说的,它就会停止稳定.

If you change the last for to what you said, it will stop being stable.

基本上,C[i] = 在第三个 for 循环结束后有多少元素 <= i 存在.所以 C[A[j]] 给你一个元素的 最后 位置,其值为 A[j] 按排序顺序,C[A[j]] - 1 具有值 A[j] 的元素的倒数第二位置,依此类推.这就是您在 C 中递减值的原因.

Basically, C[i] = how many elements <= i exist after the end of the third for loop. So C[A[j]] gives you the the last position of an element with value A[j] in sorted order, C[A[j]] - 1 the second last position of an element with value A[j] and so on. This is why you decrement the values in C.

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

Because of this, you have to start iterating your original array in reverse order if you care about stability: so that the last element with value x in your original array gets put first in the new array. Iterating your original array in reverse will guarantee that x is put after all other values equal to x, thus making the algorithm stable.

这篇关于关于计数排序算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆