c语言中,计数排序算法如何将累计数组转化为结果数组,请编写一段代码
时间: 2024-05-10 16:21:24 浏览: 66
计数排序的累计数组记录了每个元素在排序后的位置,最后需要将累计数组转化为结果数组。
以下是一个简单的示例代码:
```c
void count_sort(int arr[], int n) {
int max_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
}
int count[max_val + 1];
for (int i = 0; i <= max_val; i++) {
count[i] = 0;
}
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
for (int i = 1; i <= max_val; i++) {
count[i] += count[i - 1];
}
int result[n];
for (int i = n - 1; i >= 0; i--) {
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
}
```
在转化累计数组为结果数组时,需要从后往前遍历原数组,按照累计数组中的位置将元素插入到结果数组中。插入一个元素后,需要将其在累计数组中的计数减一。遍历完成后,将结果数组复制回原数组。
阅读全文