c - 几十年的桶装 C 程序

Question

随机给你 15 个出生在 20 世纪 (1900 - 1999) 的人的出生年份。您将获得以下数组形式的数据，这是 BucketSort 函数中使用的唯一参数:

birthYears[] = {84, 51, 92, 72, 17, 62, 1, 16, 10, 28, 99, 71, 45, 18, 61};

您的函数将具有返回类型 void 并将以下列方式工作:

• 创建一个 10x 10 数组，它将代表十年，并将其命名为 decade。因此，decade[0][1] -> decade[0][9] 将代表 00，decade[1][0] -> decade[1][9] 将代表 10，依此类推直到 decade[9][0] -> decade[9] [9] 代表 90 年代。
• 初始化您的数组，使其仅包含 -1。
• 现在遍历数组 birthYears 并将每个元素放入其适当的桶中，并放入 decade 数组中其适当的索引(观看索引)中。
• 最后，遍历几十年，一次删除一个元素并放回数组birthYears。它们应该已经按照正确的顺序排列。

这是我目前所拥有的:

void Bucket_Sort(birthYears[]){  
    int i,j;    
    int decades[10][10];
    for(i=0; i<15; i++)
}

//Actual Bucket Sort Function

void Bucket_Sort(int array[], int n){  
    int i, j;  
    int count[n];

    for (i = 0; i < n; i++)
        count[i] = 0;

    for (i = 0; i < n; i++)
        (count[array[i]])++;

    for (i = 0, j = 0; i < n; i++)  
        for(; count[i] > 0; (count[i])--)
           array[j++] = i;
}

我不确定如何进行。

Answer 1

如果我理解你的分配正确，那么我会将 birthYear 值分配到 10x10 数组中，然后将它们写回(现在订购)到 birthYear-数组。请注意，桶排序实际上需要每十年进行一次排序，但是您的分配使它变得更简单一些；关于数据，似乎每个生日只出现一次。鉴于此，代码可能如下所示:

void Bucket_Sort(int array[], int n) {

    // init decades array
    int decades[10][10];
    for(int dec=0;dec<10;dec++) {
        for(int year=0;year<10;year++) {
            decades[dec][year]=-1;
        }
    }

    // distribute array values to decades array
    for(int i=0; i<n; i++) {
        int val = array[i];
        int dec = val/10;
        int year = val%10;
        decades[dec][year]=val;
    }

    // write back
    int target = 0;
    for(int i=0; i<100; i++) {
        int dec = i/10;
        int year = i%10;
        int val = decades[dec][year];
        if (val>=0) {
            array[target++] = val;
        }
    }
}