计数排序——效率

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

Answer 1

我认为你的版本是更好的方法。我怀疑编写此代码示例的人可能已经为其他排序算法编写了类似的代码示例 — 有许多排序算法，您 do 需要单独的 "scratch space" — 而没有没有对这个考虑足够。

或者，(s)他可能觉得如果我们将 "generating the result" 与 "moving the result into place" 分开，算法更容易解释？我不同意，如果是的话，但是详细的评论清楚地表明他（她）有教学法。

也就是说，您的版本存在一些小问题：

您忘记申报 i。
您应该将 array-length 作为参数，而不是使用硬编码的 ARRAY_SIZE。（在代码示例中，通过使用字符串避免了这个问题，因此他们可以迭代直到终止空字节。）
这可能是主观的，但比起while ( countingArray[i]-- )，我觉得写for (int j = 0; j < countingArray[i]; ++j).

Answer 2

对于对整数数组进行排序的简单情况，您的代码更简单更好。

然而，计数排序是一种通用的排序算法，可以根据要排序的项目派生的排序键进行排序，用于比较它们，而不是直接比较项目本身。如果是整数数组，item和sort key可以相同，直接比较就可以了。

在我看来，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 是一个根据项目计算排序键的函数（对于整数类型，您可以 return 整数本身）。在这种情况下，MAX_NUM 必须替换为 MAX_KEY。

这种方法使用了额外的输出数组，因为最终结果是通过从 arr 中复制项目而不是简单地从 count 中的信息生成的（它只包含每个项目的计数）钥匙）。但是，in-place counting sort 是可能的。

该算法还保证 stable sort（具有相同排序键的项目通过排序保留其相对顺序） - 这在对整数排序时毫无意义。

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

他们也有可能从 C++ 等语言复制了代码，其中 int 类型转换（在使用项目索引数组时将被调用）可以重载到 return 排序键, 但错误地转换为 C.

计数排序——效率

Counting sort - Efficiency

algorithm

sorting

counting-sort