时间戳

首页 > 解决方案 > 在计数排序中为什么我们必须存储计数数组元素的累积和

algorithm - 在计数排序中为什么我们必须存储计数数组元素的累积和

问题描述

for (int i = 1; i <= max; i++)
{
    c[i] = c[i] + c[i - 1];
}

这是代码，但我不明白为什么要累积元素的总和。

标签： algorithmsortingcounting-sort

解决方案

计数排序算法用于对属于给定范围的元素序列进行排序。具体而言，假设我们正在对包含在区间 中的自然数子集进行排序[min, max]。

要理解算法，从我们想要获得的结果开始是很有用的。所以，让我们假设有序序列看起来像

m1, m1, m1, ..., m1, m2, m2,...,m2,.... m_l, m_l,..., m_l
|----------------|   |-----------|      |--------------|
      k1 times          k2 times           k_l times

换句话说，我们的有序序列包含元素m1 k1时间、元素m2 k2时间等，并且m1 < m2 < ... < m_l。

如果你想为上面序列的每个元素分配一个位置索引，你会得到

index                 element
1                     m1
2                     m1
....
k1                    m1
k1+1                  m2
k1+2                  m2
....
k1+k2                 m2
....
k1+k2+...+k_(l-1)+1   m_l
k1+k2+...+k_(l-1)+2   m_l
....
k1+k2+...+k_(l-1)+k_l m_l

从该表中可以看出，每个m_i重复k_i次数的元素 出现的索引从k1+...+k_(i-1)+1到sum_i=k1+...+k_i，其中sum_i是直到索引的频率之和i。

计数排序算法正是以这种方式工作的。

  • 您首先确定每个元素的频率（数字k_i）。使用 range [min,max]，您可以获得一组max-min+1频率（其中一些可能为零）。
  • sum_i然后，您计算每个s的部分总和，k_j直到给定索引i

  • 然后输出排序后的序列，循环遍历索引，从i=1到i=max-min+1。对于每个索引i，这样k_i > 0：

    a）您将位置设置m_i为sum_i

    b) 减少sum_i1

    c) 重复 a) 和 b) 直到sum_i==0

推荐阅读