计数排序C语言代码
简介
计数排序是一种基于比较的整数排序算法，它的核心思想是通过确定每个元素前面有几个元素来确定它的位置。由于计数排序不涉及元素之间的比较，所以它在某些情况下可以达到线性时间复杂度O(n)的效果。
在计数排序中，我们需要先确定待排序数组中的最大值max和最小值min，然后创建一个长度为(max-min+1)的辅助数组count，并将数组中的元素逐个进行计数。最后，我们根据count数组的累计值得到每个元素的正确位置，并将它们按序放回原始数组中，即可完成排序。
下面是计数排序的C语言代码实现：
#include <stdio.h>
void countingSort(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int range = max - min + 1;
    int count[range];
    for (int i = 0; i < range; i++) {
        count[i] = 0;
    }
   
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arrc语言数组最大值最小值[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}
int main() {
    int arr[] = {4, 2, 5, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
代码解析
确定最大值和最小值
首先，在实现计数排序之前，我们需要通过遍历待排序数组来确定其中的最大值和最小值。这是因为我们需要创建一个辅助数组count，其长度为最大值与最小值之差加1。
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
    if (arr[i] < min) {
        min = arr[i];
    }
}
计数
接下来，我们创建一个长度为(max-min+1)的辅助数组count，并将数组中的元素进行计数。
int range = max - min + 1;
int count[range];
for (int i = 0; i < range; i++) {
    count[i] = 0;
}
for (int i = 0; i < n; i++) {
    count[arr[i] - min]++;
}
累计计数
然后，我们对count数组进行累加操作，以确定每个元素的正确位置。
for (int i = 1; i < range; i++) {
    count[i] += count[i - 1];
}
排序
接着，我们创建一个与原始数组大小相等的输出数组output，并根据count数组的累计值，将每个元素按序放入output数组中。
int output[n];
for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
}
更新原始数组
最后，我们将排好序的output数组中的元素重新赋值给原始数组arr。
for (int i = 0; i < n; i++) {
    arr[i] = output[i];
}
示例运行结果
经过计数排序后，原始数组arr将被排序为{1, 2, 3, 4, 5}。
Sorted array:
1 2 3 4 5
总结
计数排序是一种高效的整数排序算法，适用于对具有一定范围的整数数组进行排序。它通过计数每个元素出现的次数，并确定每个元素的正确位置，从而完成排序。
计数排序的时间复杂度为O(n+k)，其中n为数组长度，k为待排序数组中的最大值与最小值之
差。由于计数排序不涉及元素之间的比较，所以它在某些情况下可以达到线性时间复杂度的效果。
此外，计数排序是稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
因此，计数排序在一些实际应用场景中具有较好的排序性能，特别适用于对整数数组进行排序。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。