我在计数排序方面遇到问题。当我对表进行排序时,有时它可以工作,但有时不行(当 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;
}
感谢您的所有帮助。
最佳答案
至少这段代码:
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 -我想是发生率)。
关于C 中的计数排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13349915/