c - 桶排序+插入排序算法中的段错误

Question

我想知道为什么我为桶排序实现的这个算法会导致段错误。看起来实现中的一切都运行良好，但可能有一些变量 n 应该是 n+1 或其他；我在解决这个问题时遇到了一些困难。

我正在按照this video中的描述来实现它.

#include <stdio.h>
#include <stdlib.h>

void insertion(int * array, int n){
    // insertion sort
    int i = 1, j = 0, temp;
    while(i < n){
        j = i;
        while(j > 0 && array[j-1] > array[j]){
            temp = array[j-1];
            array[j-1] = array[j];
            array[j] = temp;
            --j;
        }
        ++i;
    }
}

void bucket(int * array, int n){
    int max,i,j,k,size, div, pos;
    int ** buckets, *bucket_position;

    //Find maximum value in array
    max = array[0];
    for(i=0;i<n;++i) if( max < array[i] ) max = array[i];

    //Determine amount of buckets and creates them
    size = max / n;
    buckets = (int**) malloc(sizeof(int*) * size);
    for(i=0;i<size;++i){
        buckets[i] = (int*) malloc(sizeof(int) * max);
    }
    bucket_position = (int*) malloc(sizeof(int) * size);
    for(i=0;i<size;++i) bucket_position[i] = 0;

    //Copy array values into the buckets
    div = (max+1) / size;
    if( (max+1) % size ) ++div;
    for(i=0;i<n;++i){
        pos = array[i] / div;
        buckets[pos][bucket_position[pos]] = array[i];
        ++bucket_position[pos];
    }

    //Take values out of the buckets into the array
    k = 0;  
    for(i=0;i<size;++i){
        for(j=0;j<=bucket_position[i];++j){
            array[k] = buckets[i][j];
            ++k;
        }
    }

    //Do insertion sort over the array
    insertion(array,n);
}

int main(){
    int array[5] = {24354,95023,439052,934851};
    int n = 5;
    bucket(array,n);
    return 0;
}

程序输出是段错误而不是排序数组。

Answer 1

您想要对包含 n == 5 个元素的数组进行排序，其最大 vlaue 为:

max == 934851

然后计算桶的数量:

size = max / n == 186970

现在您尝试为 186970 个存储桶分配内存，每个存储桶可容纳 934851 个元素:

buckets = (int**) malloc(sizeof(int*) * size);

for (i = 0; i < size; ++i) {
    buckets[i] = (int*) malloc(sizeof(int) * max);
}

大约为 651 GB。由于有如此多的大型分配，系统很可能无法提供更多内存。因此，您应该检查从 malloc 返回的指针是否为 NULL。这就是发生的情况:您的数组索引是合法的，但动态分配的数组是NULL。

当然，您不需要那么多内存来对五个元素进行排序。对于这么小的数组，你根本不需要使用桶；立即使用插入排序。

对于较大的数组，存储桶的数量基于元素的数量，而不是最大值。在最坏的情况下，所有元素都会放入一个存储桶中，该存储桶将包含 n 个元素。因此，您也不需要 max 来确定此处的大小。

但是，您应该使用您的程序没有的 max 和 min 来计算存储桶索引:

index = (a[i] - min) * nbuckets / (max + 1 - min)

请注意此处可能出现的算术溢出。 (+ 1 确保最大元素不会获得无效索引 n。)