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

[forrestchang]

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

代码如下：

``` c++
#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()`这个函数中的代码改成这样，程序可以正确执行：

``` c++
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 多谢，刚刚自己也发现了。