0

我对计数排序有疑问。当我对表格进行排序时，有时它会起作用，但有时不会（当 k == 大小时它不起作用），我不知道为什么。请帮忙。这是我的代码：

#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;
}

谢谢大家的帮助。

4

1 回答 1

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-1i1..ktabCtabA0..k

于 2012-11-12T19:38:53.460 回答