0

我应该用 C 编写一个算法，该算法采用任何基数（基数）的整数数组，并使用基数排序将它们按升序排列。我的算法不能对数组的长度、位数和基数施加任何限制。当我说整数时，我并不是说我总是会收到一个ints 数组，它可以是一个long ints、chars、char指针等的数组。

看到这一点，我虽然处理对我的算法施加尽可能少的限制的最佳方法是通过访问向量的位置并将值类型转换到那里来处理向量，long unsigned int因此这种方法的限制是用户必须使用符合编译代码的编码选项的数字“权重”，即x十进制基数的 ASCII 编码是 120 和a97，因此如果给定的基数使用数字x和a，则x必须大于a。

这是我的算法：

/*!
 *  @function   radixSort
 *  @abstract   Sort a vector using Radix Sort.
 *  @discussion This function take a vector of positive
 *              integers in any base (radix) and sorts
 *              it in ascending order using the Radix
 *              Sort algorithm.
 *  @param      v       the vector with elements to sort
 *  @param      n       the length of the vector v
 *  @param      getMax  the function to get the maximum element of v
 */
void radixSort(void *v[], long unsigned int n, long unsigned int (*getMax)(void*[], long unsigned int)) {
    long unsigned int i;
    void* semiSorted[n];
    long unsigned int significantDigit = 1;
    long unsigned int max = (*getMax)(v, n);
    while (max / significantDigit > 0){
        long unsigned int intermediate[10] = {0};
        for(i=0; i<n; i++)
            intermediate[(long unsigned int)v[i]/significantDigit % 10]++;
        for(i=1; i<10; i++)
            intermediate[i] += intermediate[i-1];
        for(i=n; i>0; i--)
            semiSorted[--intermediate[(long unsigned int)v[i-1]/significantDigit % 10]] = v[i-1];
        for(i=0; i<n; i++)
            v[i] = semiSorted[i];
        significantDigit *= 10;
    }
}

该算法适用于我测试的所有类型，但字符串数组除外。如果我有类似的东西：

int main() {
    char *b36v[7] = {"014", "000", "8f6", "080", "056", "00a", "080"};
    printf("b36v unsorted: "); for(i=0; i<7; i++) printf("%s ", b36v[i]); printf("\n");
    radixSort(b36v, 7, getMaxFunc);
    printf("b36v sorted  : "); for(i=0; i<7; i++) printf("%s ", b36v[i]); printf("\n");
    return 0;
}

结果输出将是：

b36v 未排序：014 000 8f6 080 056 00a 080

b36v 排序：014 000 8f6 080 080 056 00a

所以它没有按预期工作，我希望排序的向量是：

000 00a 014 056 080 080 8f6

我只能看到相等的条目按预期组合在一起。更改值并观察输出我认为该算法可能正在获取内存地址并对它们进行排序，因为在原始向量的给定位置没有实际值，而是一个char's 数组。

我只是想知道是否有某种方法可以处理这些 2D（甚至 3D、4D、...）数组的情况，编写一个通用代码来处理从int/数组到数组数组的char数组......long unsigned int要求太多参数。我不知道如何在 C 中处理这种情况。

4

0 回答 0