C-为什么此计数排序返回输入而不是排序表

Question

我正在写入计数。n是表格中要排序的元素的数量，k是该元素可以是的最大值。但是，此代码使我的表格与输入相同。怎么了？

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

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

• int *result = (int *)malloc(n * sizeof(int*));使用不正确的大小。数组元素类型是int，而不是int*。你应该写：

  int *result = (int *)malloc(n * sizeof(int));
  

  或更好：

  int *result = (int *)malloc(n * sizeof(*result));
  

  还请注意，与C 不同的情况不同，演员是无用的：

  int *result = malloc(n * sizeof(*result));
  

• 您可以使用calloc()避免额外的初始化循环：

  int *counters = calloc(n, sizeof(*counters));
  

• 一个主要问题：结果数组永远不会返回到呼叫者：tab = result;只是修改参数值，而不是呼叫者的变量。相反，您应该使用tab数组直接存储结果。

• 您没有释放阵列，导致内存泄漏。

• 您不会测试分配成功的测试，如果没有内存，则会导致不确定的行为。您应该返回指示此潜在问题的错误状态。

这是一个更正的版本：

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

Answer 2

您通过指针将选项卡传递给该功能。但是，您不需要更改变量的值，而需要更改该变量的地址。因此，您应该将指针的地址传达给Countingsort。

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