为什么这个计数排序 return 输入而不是排序 table？

Question

我正在用C写计数排序。N是table中要排序的元素的个数，k是这个元素中任何一个的最大值。但是，这段代码给我留下了与输入相同的 table 。怎么了？

void countingSort(int *tab, int n, int k) {
    int *counters = (int *)malloc(k * sizeof(int));
    int *result = (int *)malloc(n * sizeof(int*));
    for (int i = 0; i < k; i++) {
        counters[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        counters[tab[i]]++;
    }
    int j = 0;
    for (int i = 0; i < k; i++) {
        int tmp = counters[i];
        while (tmp--) {
            result[j] = i;
            j++;
        }
    }
    tab = result;
}

Answer 1

您通过指针将制表符传递给函数。但是，您需要更改的不是变量的值，而是变量的地址。因此，您应该将指针的地址传递给 countingSort。

void countingSort(int **tab, int n, int k)

Answer 2

您的代码中存在一些问题：

int *result = (int *)malloc(n * sizeof(int*)); 使用了不正确的尺寸。数组元素类型是int，不是int*。你应该写：
```
int *result = (int *)malloc(n * sizeof(int));
```
或更好：
```
int *result = (int *)malloc(n * sizeof(*result));
```
另请注意，强制转换在 C 中是无用的，这与强制转换的 C++ 不同：
```
int *result = malloc(n * sizeof(*result));
```
您可以使用 calloc():
来避免额外的初始化循环
```
int *counters = calloc(n, sizeof(*counters));
```
一个主要问题：结果数组永远不会 returned 给调用者：tab = result; 只是修改参数值，而不是调用者的变量。您应该改为使用 tab 数组直接存储结果。
你没有释放数组，导致内存泄漏。
您没有测试分配是否成功，如果内存不可用会导致未定义的行为。您应该 return 指示此潜在问题的错误状态。

这是更正后的版本：

// assuming all entries in tab are > 0 and < k
int countingSort(int *tab, int n, int k) {
    int *counters = calloc(k, sizeof(*counters));
    if (counters == NULL)
        return -1;
    for (int i = 0; i < n; i++) {
        counters[tab[i]]++;
    }
    int j = 0;
    for (int i = 0; i < k; i++) {
        int tmp = counters[i];
        while (tmp--) {
            tab[j++] = i;
        }
    }
    free(counters);
    return 0;
}

为什么这个计数排序 return 输入而不是排序 table？

Why this counting sort return input instead of sorted table?

c

counting-sort