计数排序：为什么我们需要以前的计数之和？

Question

我正在阅读有关计数排序的算法，其中一个步骤是

for(i = 1 to k) 
   c[i] = c[i]+c[i-1];

为什么我们需要这一步？

为什么我们不能使用它

for(i = 0 to k)
    while(c[i]--)
        Output i/Use i as key.

我想到的一个问题是，我们是否需要数据本身（可能就像引用特定索引的字符串一样）。

但是之后，我们可以使用2D向量。在这种方法中，我们将数据从0到99进行排序有什么不好的地方。

int a[100];
for(int i = 0 ; i < 100; ++i)
    a[i] = 0;
string s;
vector<vector<string>> data(100);
int temp;
for(int i = 0 ; i < n ; ++i){
    cin>>temp;
    a[temp]++;
    getline(cin,s);
    data[temp].push_back(s);
}

for(int i = 0 ; i < 100; ++i){
    int current = 0;
    while(a[i]--){
        cout<<data[i][current]<<" ";
        ++current;
    }
}

Answer 1

在两种情况下，您可能要使用计数排序。首先，您可能有一个要排序的实际数字数组，目标是对这些数字进行排序。其次，您可能有一个要排序的值数组，每个值都是根据某个键（在固定范围内为数字）排序的。

在第一种情况下-您仅对数字进行排序-没有理由将直方图转换为累积直方图。由于数字只是数字，因此您可以对数组进行排序，而不是通过将初始值重新排列为已排序的顺序，而只需根据频率直方图生成新的数字列表即可。例如，这是您可能的操作方式：

/* Initialize histogram. */
const unsigned kMaxValue = 100;
std::vector<unsigned> counts(kMaxValue);

/* Read values. */
const unsigned kNumValues = 100;
for (unsigned i = 0; i < kNumValues; i++) {
    unsigned nextValue;
    std::cin >> nextValue; // Don't forget error-checking!

    counts[nextValue]++;
}

/* Output values. */
std::vector<unsigned> result;
result.reserve(kNumValues);
for (unsigned i = 0; i < counts.size(); i++) {
    for (unsigned j = 0; j < counts[i]; j++) {
        result.push_back(i);
    }
}

请注意，result不会从输入中读取添加到向量的数字，而是仅通过使用循环计数器来生成。

在第二种情况下-您有要排序的元素，而每个元素都有一个键-无法使用上述方法，因为您不能仅通过计数来重新生成元素。相反，您将需要做一些更聪明的事情，实际上涉及重新排列输入序列中的元素。

这就是频率直方图概念出现的地方。基本思想如下：我们要为输入数组中的每个元素确定该元素应在已排序数组中结束的索引。假设我们从获取输入数组的频率直方图H开始。该直方图的性质是H [i]告诉我们键i有多少个不同的元素。现在，假设我们制作了一个累积频率直方图C，其中C [i] = C [0] + C [1] + ... + C [i]。在这种情况下，C [i]告诉我们输入数组中有多少个元素的键小于或等于它。

假设您只有输入数组和累积频率直方图。你能用它做什么？好吧，假设您有原始数组中的一些元素A [i]。根据累积频率直方图，我们知道数组中有C [i]个元素的键小于或等于A [i]。因此，如果我们想对输入数组进行重新排序，以便所有内容都按排序顺序排列，则可以将元素A [i]放在位置C [key（A [i]）]-1处，因为存在C [key（A [ i]]]-1个小于或等于它的元素。假定数组中没有重复的值，则在数组A上进行迭代并根据此公式重新放置所有内容将正确地将数组按排序顺序放置。

如果我们有重复的话，事情会更加复杂。假设有两个元素A [i]和A [j]，其中key（A [i]）= key（A [j]）。在这种情况下，我们不能将两个元素都放置在位置C [key（A [i]）]-1处，因为它们会发生碰撞。但是，我们可以执行以下操作。我们将其中一个元素放置在位置C [key（A [i]）]-1上，然后通过从C [key（A [i]）]中减去1来破坏性地修改C数组。然后，当我们看到元素A [j]时，将其放置在位置C [key（A [j]）]-1处，这是一个空插槽。凭直觉，具有累积频率直方图的整个想法是能够通过使用给定键存储在任何特定项目之前将出现多少个对象，从而立即知道将对象定位在何处。每次我们看到带有钥匙的物品时，我们都想指出，对于任何将来使用相同钥匙的物品，

那么为什么要向后扫描呢？我们可以很容易地进行正向扫描，但是向后扫描的优点是可以稳定地对元素进行排序。也就是说，如果您有多个具有相同键的元素，它们在输出序列中的出现顺序将与在输入序列中的出现顺序相同。

这是一些代码，展示了如何使用它：

/* Initialize histogram. */
const unsigned kMaxValue = 100;
std::vector<unsigned> counts(kMaxValue);

/* Read values. Each value will be a string with an associated key. */
const unsigned kNumValues = 100;
std::vector<std::pair<unsigned, std::string>> elems;
elems.reserve(kNumValues);

for (unsigned i = 0; i < kNumValues; i++) {
    unsigned key;
    std::cin >> key; // Don't forget error-checking!

    std::string value;
    std::cin >> value;       // Don't forget error-checking!
    elems.push_back(std::make_pair<key, value>);

    counts[key]++;
}

/* Transform histogram into cumulative histogram. */
for (unsigned i = 1; i < counts.size(); i++) {
   counts[i] += counts[i - 1];
}

/* Output values. */
std::vector<unsigned> result(kNumValues);
for (unsigned i = counts.size() - 1; i >= 0 && i < counts.size(); i--) { // See note
    result[--counts[elems[i].first]] = elems[i].second;
}

由于使用无符号值向下计数，因此循环有些奇怪。这个问题详细说明了如何正确处理。