c - 提高我实现计数排序的时间复杂度(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.