计数排序 - 为什么在插入过程中按相反的顺序进行？

Question

我在 GeeksForGeeks 上查看了计数排序的代码，在算法的最后阶段，原始数组中的元素被插入到排序数组中的最终位置（第二个到-last for循环），输入数组倒序遍历

我似乎不明白为什么你不能像这样从输入数组的开头到结尾：

for i in range(len(arr)): 
        output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] 
        count_arr[arr[i] - min_element] -= 1

是否有一些我遗漏的相反顺序的微妙原因？如果这是一个非常明显的问题，我们深表歉意。我也看到了以相同样式 here 实现的计数排序。

任何意见都会有帮助，谢谢！

Answer 1

Stability。按照您的方式，equal-valued 元素的顺序被颠倒而不是保留。向后遍历输入会取消向后复制（-= 1 事情）。

Answer 2

要以正向顺序处理数组，计数/索引数组需要大一个元素以便起始索引为 0，或者可以使用两个局部变量。整数数组示例：

def countSort(arr): 
    output = [0 for i in range(len(arr))] 
    count = [0 for i in range(257)]         # change
    for i in arr: 
        count[i+1] += 1                     # change
    for i in range(256):
        count[i+1] += count[i]              # change
    for i in range(len(arr)): 
        output[count[arr[i]]] = arr[i]      # change
        count[arr[i]] += 1                  # change
    return output

arr = [4,3,0,1,3,7,0,2,6,3,5]
ans = countSort(arr) 
print(ans)

或者使用两个变量，s 保存运行总和，c 保存当前计数：

def countSort(arr): 
    output = [0 for i in range(len(arr))] 
    count = [0 for i in range(256)]
    for i in arr: 
        count[i] += 1
    s = 0
    for i in range(256):
        c = count[i]
        count[i] = s
        s = s + c
    for i in range(len(arr)): 
        output[count[arr[i]]] = arr[i]
        count[arr[i]] += 1
    return output

arr = [4,3,0,1,3,7,0,2,6,3,5]
ans = countSort(arr) 
print(ans)

Answer 3

Here We are Considering Stable Sort --> 这实际上是逐个位置考虑元素。

例如，如果我们有这样的数组

arr--> 5 ,8 ,3, 1, 1, 2, 6

     0 1 2 3 4 5 6 7 8

计数-> 0 2 1 1 0 1 1 0 1

现在我们对所有频率求和

     0 1 2 3 4 5 6 7 8

计数-> 0 2 3 4 4 5 6 6 7

遍历原数组后，我们更喜欢从上一个Since 我们想在适当的位置添加元素，所以当我们减去索引时，元素将被添加到横向位置。

但是如果我们从头开始遍历，那么累加和就没有意义了，因为我们不是按照放置的元素进行相加。我们正在添加 hap -hazardly，即使我们不取他们的累计总和也可以完成。

计数排序 - 为什么在插入过程中按相反的顺序进行？

Counting Sort - Why go in reverse order during the insertion?

sorting

counting-sort