c - 为什么这个计数排序返回输入而不是排序表？

Question

我正在用 C 编写计数排序。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 中是无用的，这与强制转换的 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;
}