计数排序显示奇怪的行为

Question

我在老师给我们的作业中实现了计数排序，但有时它不适用于大型数组。

代码如下:

void countingSort(int *t, int n) {
    int min = findMin(t, n);
    int max = findMax(t, n);
    int range = max - min + 1;
    int *count, *output;
    int i;
    count = (int *)malloc(range * sizeof(int));
    output = (int *)malloc(n * sizeof(int));

    for (i = 0; i < range; i++) {
        count[i] = 0;
    }
    for (i = 0; i < n; i++) {
        count[t[i] - min]++;
    }
    for (i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        output[count[t[i] - min] - 1] = t[i];
        count[t[i] - min]--;
    }
    for (i = 0; i < n; i++) {
        t[i] = output[i];
    }
}

我的代码有什么问题？

Answer 1

您的代码似乎适用于 range 的小值，但如果 min 和 max 相距太远，可能会导致计算失败range 溢出 int 的范围，malloc() 失败。

您应该检查 range 是否溢出并检查内存分配是否成功。另请注意，对于 count 数组，calloc() 比 malloc() 更合适。最后，您必须释放分配的数组。

修改后的版本:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int findMax(const int *t, int n) {
    int max = INT_MIN;
    while (n-- > 0) {
        if (max < *t) max = *t;
        t++;
    }
    return max;
}    

int findMin(const int *t, int n) {
    int min = INT_MAX;
    while (n-- > 0) {
        if (min > *t) min = *t;
        t++;
    }
    return min;
}    

int countingSort(int *t, int n) {
    int min, max, range, i;
    int *count, *output;

    if (n <= 0)
        return 0; 

    min = findMin(t, n);
    max = findMax(t, n);

    if (min < 0 && max >= 0 && (unsigned)max + (unsigned)(-min) >= INT_MAX) {
        fprintf(stderr, "countingSort: value range too large: %d..%d\n", min, max);
        return -1;
    }
    range = max - min + 1;
    if ((count = (int *)calloc(range, sizeof(int))) == NULL) {
        fprintf(stderr, "countingSort: cannot allocate %d element count array\n", range);
        return -1;
    }
    if ((output = (int *)malloc(n * sizeof(int))) == NULL) {
        fprintf(stderr, "countingSort: cannot allocate %d element output array\n", n);
        free(count);
        return -1;
    }
    for (i = 0; i < n; i++) {
        count[t[i] - min]++;
    }
    for (i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    for (i = n; i-- > 0;) {
        output[count[t[i] - min] - 1] = t[i];
        count[t[i] - min]--;
    }
    for (i = 0; i < n; i++) {
        t[i] = output[i];
    }
    free(count);
    free(output);
    return 0;
}

您可以通过将第二个和第三个 for 循环替换为以下代码来避免繁琐且可能效率低下的向下循环:

    /* compute the first index for each value */
    int index = 0;
    for (i = 0; i < range; i++) {
        incr = count[i];
        count[i] = index;
        index += incr;
    }
    /* copy each value at the corresponding index and update it */
    for (i = 0; i < n; i++) {
        output[count[t[i] - min]++] = t[i];
    }