我在考虑计数排序以及我们如何实现它，实际上是算法如何工作的。我被一部分卡住了，算法非常简单易懂，但其中一部分似乎没有必要。我以为人们可能搞错了，但似乎每个人都用同样的方法，所以我在某个地方弄错了。你能解释一下吗。
以下是来自极客的计数排序代码
// 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 %sn", 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,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;
}
对于对整数数组进行排序的简单情况，您的代码越来越简单。
然而，计数排序是一种通用的排序算法，它可以根据从要排序的项目派生的排序键进行排序，该排序键用于比较它们，而不是直接比较项目本身。在整数数组的情况下，项和排序键可以是同一个，只需直接比较即可。
在我看来，极客代码似乎是从一个更通用的例子中改编而来的，这个例子允许使用排序键，比如
// 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是一个基于项计算排序键的函数(对于整数类型，您可以只返回整数本身)。在这种情况下，CCD_ 2将不得不被CCD_。
这种方法使用额外的输出数组，因为最终结果是通过复制arr中的项而不是简单地从count中的信息(它只包含每个键的项计数)生成的。然而，就地计数排序是可能的。
该算法还保证了稳定的排序(具有相同排序键的项目通过排序保持其相对顺序)——这在对整数排序时没有意义。
然而，由于他们已经取消了根据关键字进行排序的功能，所以没有理由增加复杂性，而且您的方法更好。
也有可能是他们从C++这样的语言复制了代码，在C++中，int强制转换(使用项索引数组时会调用它)可能会被重载以返回排序键，但错误地转换为C.
我认为您的版本是一种更好的方法。我怀疑写这个代码示例的人可能为其他排序算法写过类似的代码示例——有很多排序算法，你确实需要单独的"暂存空间"——并且没有对这个算法进行足够的思考。
或者，如果我们将"生成结果"与"将结果移动到位"分开，他可能会觉得算法更容易解释？如果是的话，我不同意，但详细的评论清楚地表明，他考虑到了教育学。
也就是说，你的版本有一些小问题：
- 您忘记声明
i - 您应该将数组长度作为一个参数，而不是使用硬编码的
ARRAY_SIZE。(在代码示例中，通过使用字符串可以避免此问题，因此它们可以迭代到终止的null字节。) - 这可能是主观的，但我认为写
for (int j = 0; j < countingArray[i]; ++j)比写while ( countingArray[i]-- )更清楚