有关《算法导论》第 8 章「计数排序」的一个问题

[forrestchang]

最近在看《算法导论》，在用 C++ 实现第 8 章中的「计数排序」时遇到了一个问题。

代码如下：

#include <iostream>
#include <cstdlib>

using namespace std;

void countingSort(int array[], int arraySize, int result[], int k);
int max(int array[], int arraySize);

int main(void) {
  int testArray[1000];
  int resultArray[1000];
  int arraySize;

  cin >> arraySize;
  for (int i = 0; i < arraySize; i++) {
    cin >> testArray[i];
  }

  int k = max(testArray, arraySize);
  countingSort(testArray, arraySize, resultArray, k);

  for (int i = 0; i < arraySize; i++) {
    cout << resultArray[i] << " ";
  }
  cout << endl;

  return 0;
}

int max(int array[], int arraySize) {
  int largest = array[0];
  for (int i = 0; i < arraySize; i++) {
    largest = largest > array[i] ? largest : array[i];
  }

  return largest;
}

void countingSort(int array[], int arraySize, int result[], int k) {
  int * countArray = (int *)malloc((k + 1) * sizeof(int));
  int countArraySize = k + 1;

  // 初始化临时数组为 0
  for (int i = 0; i < countArraySize; i++) {
    countArray[i] = 0;
  }

  // 如果一个输入元素的值为 i ，则对应增加 countArray[i]的值， countArray[i]中保存的是元素 i 的个数
  for (int i = 0; i < arraySize; i++) {
    countArray[array[i]]++;
  }

  // 包含小于或等于 i 个元素的个数
  for (int i = 1; i < countArraySize; i++) {
    countArray[i] += countArray[i - 1];
  }

  for (int i = arraySize - 1; i >= 0; i--) {
    result[countArray[array[i]]] = array[i];
    countArray[array[i]]--;
  }
}

因为《算法导论》的数组下标都是从 1 开始的，于是就自己转换了一下，但是程序的运行结果是错的（也可能是下标转换错了，但是是不清楚错在哪里）

将countingSort()这个函数中的代码改成这样，程序可以正确执行：

void countingSort(int array[], int arraySize, int result[], int k) {
  int * countArray = (int *)malloc((k + 1) * sizeof(int));
  int countArraySize = k + 1;

  // 初始化临时数组为 0
  for (int i = 0; i < countArraySize; i++) {
    countArray[i] = 0;
  }

  // 如果一个输入元素的值为 i ，则对应增加 countArray[i]的值， countArray[i]中保存的是元素 i 的个数
  for (int i = 1; i < arraySize; i++) {
    countArray[array[i]]++;
  }
  //更改处：将 i 的初始值设为 1

  // 包含小于或等于 i 个元素的个数
  for (int i = 1; i < countArraySize; i++) {
    countArray[i] += countArray[i - 1];
  }

  for (int i = arraySize - 1; i >= 0; i--) {
    result[countArray[array[i]]] = array[i];
    countArray[array[i]]--;
  }
}

但是这样改的话没有想明白，数组不应该从 0 开始遍历吗？

[Magic347]

void countingSort(int array[], int arraySize, int result[], int k) {
int * countArray = (int *)malloc((k + 1) * sizeof(int));
int countArraySize = k + 1;

for (int i = 0; i < countArraySize; i++) {
countArray[i] = 0;
}

for (int i = 0; i < arraySize; i++) {
countArray[array[i]]++;
}

for (int i = 1; i < countArraySize; i++) {
countArray[i] += countArray[i - 1];
}

for (int i = arraySize - 1; i >= 0; i--) {
result[--countArray[array[i]]] = array[i];

}

countArray[i] 表示原数组中小于等于 i 的元素个数，因此 i 在结果数组 result 中的位置应该就是 countArray[i] - 1 。

[forrestchang]

@Magic347 多谢，刚刚自己也发现了。