提高计数排序 (C) 实现的时间复杂度

Question

请考虑以下代码：

#define SIZE 12
void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);
int main(void)
{
    srand(time(NULL));
    int* array = (int*)malloc(sizeof(int) * SIZE);
    randomize(array, SIZE);
    print(array, SIZE);
    counting_sort(array, SIZE);
    free(array);
    return 0;
}
void randomize(int* array, int array_size) {...}
void print(int* array, int array_size) {...}
void counting_sort(int* array, int array_size) {
    int minVal, maxVal;
    int* sorted = (int*)malloc(sizeof(int) * SIZE);
    maxVal = get_max(array, array_size);
    int* values = (int*)malloc(maxVal * sizeof(int));
    memset(values, 0, maxVal * sizeof(int));
    for (int i = 0; i < array_size; i++) {
        values[array[i]]++;
    }
    construct(sorted, SIZE, values);
    free(values);
    free(sorted);
    }
int get_max(int* array, int array_size) {...}
void construct(int* sorted, int array_size, int* values) {
    for (int i = 0, j = 0; i < array_size; i++) {
        while (!values[++j]);
        sorted[i] = j;
        --values[j];
    }
    print(sorted, SIZE);
} 

main()声明一个数组，其大小由宏SIZE控制。然后有几个函数可以随机化、打印和查找该数组的最大值。之后是计数排序本身的实现，它使用 construct(..) 函数来创建排序数组。我已经测试了几次，找不到任何错误。然而，这就是我所关心的。

for (int i = 0, j = 0; i < array_size; i++) {
            while (!values[++j]);...

我们有 2 个内部循环，这些循环中的变量递增。这意味着construct(...)函数的时间复杂度变为二次，而不是线性。问题是我想不出一个好方法来丢弃values[]中的所有0.线性解决方案非常受欢迎。

添加了完整代码：

#include <stdlib.h>
#include <cassert>
#include <time.h>
#include <limits.h>
#include <string.h>
#define SIZE 160
void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);
int main(void)
{
    srand(time(NULL));
    int* array = (int*)malloc(sizeof(int) * SIZE);
    randomize(array, SIZE);
    print(array, SIZE);
    counting_sort(array, SIZE);
    free(array);
    return 0;
}
void randomize(int* array, int array_size) {
    for (int i = 0; i < array_size; i++) {
        array[i] = rand() % array_size;
    }
}
void print(int* array, int array_size) {
    for (int i = 0; i < array_size; i++) {
        printf("%4d ", array[i]);
    }
    putchar('n');
}
void counting_sort(int* array, int array_size) {
    int minVal, maxVal;
    int* sorted = (int*)malloc(sizeof(int) * SIZE);
    maxVal = get_max(array, array_size);
    int* values = (int*)malloc(maxVal * sizeof(int));
    memset(values, 0, maxVal * sizeof(int));
    for (int i = 0; i < array_size; i++) {
        values[array[i]]++;
    }
    construct(sorted, SIZE, values);
    free(values);
    free(sorted);
}
int get_max(int* array, int array_size) {
    int max = INT_MIN;
    for (int i = 0; i < array_size; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}
void construct(int* sorted, int array_size, int* values) {
    for (int i = 0, j = 0; i < array_size; i++) {
        while (!values[j]) {
            ++j;
        }
        sorted[i] = j;
        --values[j];
    }
    print(sorted, SIZE);
} 

Answer 1

您的实现是线性的。你有一个内部 while 循环，但 j 的值永远不会重置为 0 ，它在 for 循环的每次迭代中不断增长。总体i将从0计算到size，j将从0计算到n。