c - 不使用 vector 、指针和计数排序的桶排序实现

Question

我们要使用桶排序对1到2001之间的数字进行排序。数字的个数可以是10E6。

我知道桶排序算法。但问题是，在这道题中，我们不允许使用变长数组、 vector 和指针。 (唯一允许的与指针相关的事情是数组的“按引用传递”)我发现的唯一解决方案是对每个桶使用计数排序，如下面的代码，因此该代码更像是计数排序而不是桶排序:( 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; }

我想知道桶排序是否可以在没有变长数组、 vector 和指针的情况下实现，也可以在没有计数排序的情况下实现。可能使用插入或冒泡排序。注意，它必须是一个合理的桶排序算法。因此定义像 int bucket [201][1000000]; 这样非常大的存储桶也是一种 Not Acceptable 方法。

Answer 1

鉴于您无法使用可变长度数组或指针(桶排序需要其中之一)，因此最好的选择是使用计数排序。您只有 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]--;
    }
}