桶排序实现，无需使用向量、指针和计数排序
桶排序实现，无需使用向量、指针和计数排序
提问于 2018-11-12 21:11:27
我们希望使用桶排序来对1到2001之间的数字进行排序。数字的计数可以是10E6。
我知道桶排序算法。但问题是，在这个问题中，我们不允许使用可变长度数组、向量和指针。(唯一允许的指针相关的东西是数组的“传递引用”)我找到的唯一解决方案是对每个桶使用计数排序，就像下面的代码一样，所以代码更像是计数排序而不是桶排序：(C语言)
#include <stdio.h>
int buckets[201][10]={}; int numbers[1000001]={};
void bucket_sort (int a[],int n) {
for (int i =0;i<=n-1;i++)
{
int index = a[i]/10, index2 = a[i]%10;
buckets[index][index2]++;
}
int counter =0;
for (int i =0;i<=200;i++)
{
for (int j =0; j<=9;j++)
{
while (buckets[i][j])
{
a[counter] = i*10+j;
counter++;
buckets[i][j]--;
}
}
} }
int main() {
int n;
scanf("%d",&n);
if (n==0)
{
return 0;
}
for (int i =0;i<=n-1;i++)
{
scanf("%d",&numbers[i]);
numbers[i];
}
bucket_sort(numbers,n);
for (int i =0;i<=n-1 ;i++)
{
printf("%d\n", numbers[i]);
}
return 0; }我想知道桶排序可以在没有可变长度数组、向量和指针的情况下实现，也不需要计数排序。可能使用插入或气泡排序。请注意，它必须是一个合理的桶排序算法。因此，定义非常大的桶(如int bucket [201][1000000]; )也是一种不可接受的方法。
回答 1
Stack Overflow用户
发布于 2018-11-12 21:23:32
考虑到不能使用可变长度数组或指针(桶排序需要其中之一)，最好的选择是使用计数排序。您只有2000种可能的值，所以创建一个大小为2000的数组，对于每个值，您可以找到相应的数组元素。
void counting_sort(int a[], int n)
{
int count[2002] = { 0 };
int i, j;
for (i=0; i<n; i++) {
count[a[i]]++;
}
for (i=0, j=0; i<n; i++) {
while (!count[j]) {
j++;
}
a[i] = j;
count[j]--;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53270166
复制相关文章
相似问题
腾讯云开发者
