c - 这些功能如何运作？

Question

您能解释一下以下两种算法的工作原理吗？

int countSort(int arr[], int n, int exp)
{
    int output[n]; 
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;
    for (i = 1; i < n; i++)
        count[i] += count[i - 1];
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%n] - 1] = arr[i];
        count[(arr[i]/exp)%n]--;
    }
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}


void sort(int arr[], int n)
{
    countSort(arr, n, 1);
    countSort(arr, n, n);
}

我想在这个数组上应用算法:

调用函数 countSort(arr, n, 1) 后，我们得到:

当我调用函数 countSort(arr, n, n) 时，在这个 for 循环中:

for (i = n - 1; i >= 0; i--)
{
    output[count[ (arr[i]/exp)%n] - 1] = arr[i];
    count[(arr[i]/exp)%n]--;
}

我得到输出[-1]=arr[4]。

但是数组没有这样的位置...

我是不是做错了什么？

编辑:考虑到数组 arr[] = { 10, 6, 8, 2, 3 }，数组计数将包含以下元素:

这些数字代表什么？我们如何使用它们？

Answer 1

计数排序非常简单 - 假设您有一个数组，其中包含 1..3 范围内的数字:
[3,1,2,3,1,1,3,1,2]

您可以计算每个数字在数组中出现的次数:
计数[1] = 4
计数[2] = 2
计数[3] = 3

现在你知道在排序数组中，
数字 1 将占据位置 0..3(从 0 到 count[1] - 1)，然后通过
位置 4..5 上的数字 2(从 count[1] 到 count[1] + count[2] - 1 ), 然后是
位置 6..8 上的数字 3(从 count[1] + count[2] 到 count[1] + count [2] + count[3] - 1).

现在您知道每个数字的最终位置，您可以将每个数字插入到正确的位置。这基本上就是 countSort 函数的作用。

然而，在现实生活中，您的输入数组不会仅包含 1..3 范围内的数字，因此解决方案是先按最低有效数字 (LSD) 对数字进行排序，然后再按 LSD- 1 ... 直到最重要的数字。
通过这种方式，您可以通过对范围 0..9(十进制数字系统中的单个数字范围)中的数字进行排序来对更大的数字进行排序。
此代码:countSort 中的 (arr[i]/exp)%n 仅用于获取这些数字。 n 是您的数字系统的基础，因此对于十进制，您应该使用 n = 10 并且 exp 应该以 1 开头> 并在每次迭代中乘以基数以获得连续数字。
例如，如果我们想要从右边开始第三个数字，我们使用 n = 10 和 exp = 10^2:
x = 1234, (x/exp)%n = 2。

此算法称为基数排序，在维基百科上有详细说明:http://en.wikipedia.org/wiki/Radix_sort