计数排序 - 效率

Question

我在思考计数排序以及我们如何实现它，实际上就是算法的工作方式。我困在其中的一个部分，算法实际上非常简单易懂，但其中一部分似乎并不必要。我认为人们可能会犯错，但似乎每个人都使用相同的方法，所以我可能哪里弄错了。你能解释一下吗？

以下是来自geeksforgeeks的计数排序代码。

    // C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255

// The main function that sort the given string arr[] in
// alphabatical order
void countSort(char arr[])
{
    // The output character array that will have sorted arr
    char output[strlen(arr)];

    // Create a count array to store count of inidividul
    // characters and initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    // Store count of each character
    for(i = 0; arr[i]; ++i)
        ++count[arr[i]];

    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];

    // Build the output character array
    for (i = 0; arr[i]; ++i)
    {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }

    // Copy the output array to arr, so that arr now
    // contains sorted characters
    for (i = 0; arr[i]; ++i)
        arr[i] = output[i];
}

// Driver program to test above function
int main()
{
    char arr[] = "geeksforgeeks";//"applepp";

    countSort(arr);

    printf("Sorted character array is %s\n", arr);
    return 0;
}

很棒，但是关于这一部分：

// Build the output character array
        for (i = 0; arr[i]; ++i)
        {
            output[count[arr[i]]-1] = arr[i];
            --count[arr[i]];
        }

为什么我需要这个？好的，我数了一下我的数字：

假设我有一个数组 -> [1, 3, 6, 3, 2, 4]

注：该文本已被翻译，按原样返回即可。

         INDEXES     0  1  2  3  4  5  6
  I created this -> [0, 1, 1, 2, 1, 0, 1]

那么这个部分会执行以下操作:

  [0, 1+0, 1+1, 2+2, 4+1, 0+5, 1+5]
  [0, 1, 2, 4, 5, 5, 6]

为什么？

我不能像之前那样使用我的数组吗？这是我的想法和代码，请解释为什么它是错误的，或者为什么其他方法更有用。

void countingSort (int *arr) {

    int countingArray[MAX_NUM] = {0};

    for (i = 0 ; i < ARRAY_SIZE ; i++)
        countingArray[arr[i]]++;

    int output_Index = 0;

    for (i = 0 ; i < MAX_NUM ; i++)
        while ( countingArray[i]-- )
            arr[output_Index++] = i;
}

- user7476979

Answer 1

对于简单情况，你需要对整数数组进行排序，那么你的代码更简洁、更好。

然而，计数排序是一种通用的排序算法，可以根据源于待排序项目的排序键进行排序，该键用于比较它们，而不是直接比较项目本身。对于整数数组，项目和排序键可以是相同的，只需直接比较它们即可。

在我看来，geeksforgeeks 的代码似乎是从一个更通用的示例中进行了改编，允许使用排序键，类似于以下内容：

// Store count of each item
for(i = 0; arr[i]; ++i)
    ++count[key(arr[i])];

// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (i = 1; i <= RANGE; ++i)
    count[i] += count[i-1];

// Build the output array
for (i = 0; arr[i]; ++i)
{
    output[count[key(arr[i])]-1] = arr[i];
    --count[key(arr[i])];
}

其中key是一个基于项计算排序键的函数（对于整数类型，您可以只返回整数本身）。在这种情况下，MAX_NUM必须替换为MAX_KEY。

此方法使用额外的输出数组，因为最终结果是通过从arr复制项目而生成的，而不仅仅是从count中的信息（其中仅包含每个键具有的项目计数）生成。然而，可以进行原地计数排序。

该算法还保证了稳定的排序（具有相同排序键的项目通过排序保留其相对顺序）-这在对整数进行排序时没有意义。

然而，由于他们已经删除了基于键排序的能力，因此没有理由增加额外的复杂性，您的方式更好。

还可能他们从像C ++这样的语言中复制了代码，在那里int转换（在使用项目对数组进行索引时将调用）可以重载以返回排序键，但错误地转换为C。

- samgak

Answer 2

我认为你的版本是更好的方法。我怀疑写这段代码示例的人可能已经为其他排序算法编写了类似的代码示例 - 在许多排序算法中，您确实需要单独的“临时空间” - 并没有对此进行足够的思考。

或者，他/她可能认为，如果我们将“生成结果”与“将结果移动到指定位置”分开，那么该算法更容易解释？如果是这样，我不同意，但详细的注释清楚地表明他/她有教学方面的考虑。

话虽如此，你的版本有一些小问题：

- 你忘记声明i。 - 你应该将数组长度作为参数，而不是使用硬编码的ARRAY_SIZE。（在代码示例中，通过使用字符串来避免这个问题，因此可以迭代到终止的空字节。） - 这可能是主观的，但我认为写成for (int j = 0; j < countingArray[i]; ++j)比while (countingArray[i]--)更清晰。

- ruakh

---

更主观的，memset？ - Mooing Duck

我喜欢这个答案。尽管如此，我的代码是为了比赛而编写的，因此我通常定义变量，例如MAX_NUM实际上在主函数中定义，i也是通常定义的，如果不必要，我不喜欢在函数中放置太多参数。 - user7476979

@MooingDuck memset怎么样？ - user7476979

@BedirTapkan：while ( countingArray[i]-- ) arr[output_Index++] = i; 可以被替换为单个 memset 调用。 - Mooing Duck

@MooingDuck Maan :D 我从来没有这样使用过memset，很棒！谢谢！ - user7476979