C中的计数排序函数

Question

我尝试在C中实现计数排序算法。

你能发现什么效率？当再次运行原始数组以将排序数组分配给它时，我会斜视末尾。也许还有更好的方法？

/**
* Sorts array of n values.
* Using counting sort O(n)
*/
void sort(int values[], int n)
{
  //set our known max length, initialize our placer array and then our sorted array
  int maxLength = 65536;
  int placer[maxLength];
  int sorted[n];

  //so we can know which indexes in our placer array are in values array
  for ( int i = 0; i < n; i++ ) {
    placer[ values[i] ] += 1;
  }

  //store the sum of previous elements in each element at each index because this will give us the sorted position
  for (int i = 0; i < maxLength; i++ ) {
    placer[ i + 1 ] += placer[i];
  }

  //fill the sorted array with the values elements using the corresponding placer index
  for ( int i = 0; i < n; i++ ) {
    sorted[ placer[ values[i] ] - 1 ] = values[i];
    placer [ values[i] ] -= 1;

  }

  //set the unsorted values array to the sorted array
  for (int i = 0; i < n; i++) {
    values[i] = sorted[i];
  }
}

Answer 1

由一个错误

关闭

此循环以1结束，并写入最后一个数组元素：

对于(int i= 0；i< maxLength；i++ ){砂子I+1 +=砂子我；}

您可以在maxLength - 1停止循环，也可以重写循环，从1开始，如下所示：

  for (int i = 1; i < maxLength; i++ ) {
    placer[i] += placer[i-1];
  }

未初始化变量导致崩溃

当我运行您的程序时，由于一个未初始化的变量，它崩溃了，在这里：

国际砂矿公司maxLength；

稍后，在不将placer[values[i]] += 1数组清除为零的情况下执行placer，这样就可以在数组中获得垃圾值。您可以通过这样清除数组来修复这个问题：

memset(placer, 0, sizeof(placer));

但是，我建议不要使用可变长度数组。原因之一是它们只能在最新的C标准中可选地支持。另一个原因是，如果分配一个较大的可变长度数组，有时可能会导致堆栈溢出。我将在这里使用calloc()分配计数数组。

简化了函数

看起来，您使用的是用于基排序的计数排序版本，它需要在数组中移动元素。对于一个简单的计数类型，您不需要这样做。计数传递之后，您可以使用计数值填充原始数组，如下所示：

// Uses counting sort to sort an array which contains values in the
// range [0..65535].  The counting array is allocated using calloc() in
// order to avoid putting a large array on the stack.
void sort(int values[], int n)
{
    const int maxLength = 65536;
    int      *counts    = calloc(maxLength, sizeof(*counts));

    if (counts == NULL) {
        return;
    }

    for (int i = 0; i < n; i++) {
        counts[values[i]]++;
    }

    int outIndex = 0;
    for (int i = 0; i < maxLength; i++) {
        for (int j = 0; j < counts[i]; j++) {
            values[outIndex++] = i;
        }
    }

    free(counts);
}