c语言中,计数排序算法如何将累计数组转化为结果数组,请编写一段代码并标上注释
时间: 2024-05-24 08:11:07 浏览: 109
字符串排序算法比较(C语言)
void countingSort(int arr[], int n) {
int output[n]; // 结果数组
int max = arr[0]; // 找到最大值
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count[max + 1]; // 计数数组
for (int i = 0; i <= max; i++) {
count[i] = 0; // 初始化计数数组
}
for (int i = 0; i < n; i++) {
count[arr[i]]++; // 计数
}
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1]; // 将计数数组转化为累计数组
}
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i]; // 将元素放入结果数组
count[arr[i]]--; // 累计数组减一
}
for (int i = 0; i < n; i++) {
arr[i] = output[i]; // 将结果数组赋值给原数组
}
}
阅读全文