c++ - 计数排序 : Why we need sum of previous counts?

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 Vector。 我们从 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 vector 的数字不是从输入中读取的，而是仅通过使用循环计数器生成的。

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

这就是频率直方图思想的用武之地。基本思想如下 - 我们要为输入数组中的每个元素确定该元素在排序数组中结束时的索引。假设我们首先获取输入数组的频率直方图 H。该直方图具有 H[i] 告诉我们有多少个具有键 i 的不同元素的属性。现在，假设我们制作一个累积频率直方图 C，其中 C[i] = C[0] + C[1] + ... + C[i]。在这种情况下，C[i] 告诉我们输入数组中有多少元素的键小于或等于它。

假设您只有输入数组和累积频率直方图。你能用它做什么？好吧，假设您有一些来自原始数组的元素 A[i]。根据累积频率直方图，我们知道数组中有C[i]个元素的key小于等于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，这是一个空槽。直觉上，具有累积频率直方图的整个想法是能够通过存储有多少对象将出现在具有给定键的任何特定项目之前来立即知道将对象放置在哪里。每次我们看到一个带有某个键的项目时，我们都想表明对于任何具有相同键的 future 项目，在它之前的项目都会少一个。

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

这里有一些代码展示了如何使用它:

/* 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;
}

由于使用无符号值进行倒计时，循环有点奇怪。 This question详细说明如何正确处理。