最近在看《算法导论》，在用 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 开始遍历吗？
1
Select Language