C 中的计数排序

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

我在计数排序方面遇到问题。当我对表进行排序时，有时它可以工作，但有时不行(当 k == size 时它不起作用)，我不知道为什么。请帮忙。这是我的代码:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100000
int tabA[MAX];
int tabB[MAX];
int tabC[MAX];
int k;

void scope(int size){
int i, max = 0, min;

min = tabA[1];

    for(i = 1; i <= size; i++){
        if(tabA[i] > max)
            max = tabA[i];
        if(tabA[i] < min)
            min = tabA[i];
    }

    k = max - min + 1;
}

void rand1(int size){
    int i;
    srand(time(NULL));

    for(i = 0; i <= size; i++)
        tabA[i] = rand() % 8;
} 

void countingsort(int size){
    int i;

    for(i = 0; i < k; i++)
        tabC[i] = 0;

    for(i = 0; i < size; i++)
        tabC[tabA[i + 1]] = tabC[tabA[i + 1]] + 1;

    for(i = 1; i <= k; i++)
        tabC[i] = tabC[i] + tabC[i - 1];

    for(i = size; i >= 1; i--){
        tabB[tabC[tabA[i]]] = tabA[i];
        tabC[tabA[i]] = tabC[tabA[i]] - 1;
    }   
}

int main(void){
    int size, i;

    printf("Please write how many numbers you wont to sort: ");
    scanf("%d", &size);

    rand1(size);
    scope(size);
    countingsort(size);

    printf("Numbers to sort:\n");
    for(i = 1; i <= size; i++)
        printf("%d\n", tabA[i]);

    printf("\nK: %d\n\n", k);

    printf("Sorting numbers:\n");
    for(i = 1; i <= size; i++)
        printf("%d\n", tabB[i]);

    return 0;
}

感谢您的所有帮助。

Answer 1

至少这段代码:

for(i = 0; i < k; i++)
    tabC[i] = 0;

for(i = 0; i < size; i++)
    tabC[tabA[i + 1]] = tabC[tabA[i + 1]] + 1;

for(i = 1; i <= k; i++)
    tabC[i] = tabC[i] + tabC[i - 1];

有问题，在第一个初始化循环中 i 变为 0..k-1，但在最后一个循环中 i从 1..k 开始，假设 tabC 已初始化。另外，中间循环假设 tabA 值的范围是 0..k，但它可能不是(查看随机化函数，它实际上可能是，但这只是 co -我想是发生率)。