计数排序法c语言程序

### C语言实现计数排序算法

以下是完整的C语言计数排序算法示例代码：

#include <stdio.h>
#include <stdlib.h>

// 获取数组中的最大值
int find_max(const int *array, int size) {
    int max = array[0];
    for (int i = 1; i < size; ++i) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

// 计数排序函数
void counting_sort(int *array, int size) {
    // 寻找数组中最大的元素作为范围依据
    int max_value = find_max(array, size);
    
    // 创建并初始化计数数组
    int *count_arr = (int *)calloc(max_value + 1, sizeof(int));
    for (int i = 0; i < size; ++i) {
        count_arr[array[i]]++;
    }

    // 累加计数数组，得到偏移下标
    for (int i = 1; i <= max_value; ++i) {
        count_arr[i] += count_arr[i - 1];
    }

    // 输出临时数组
    int *output = (int *)malloc(size * sizeof(int));

    // 将原数组按照计数值放入输出数组中
    for (int i = size - 1; i >= 0; --i) {
        output[count_arr[array[i]] - 1] = array[i];
        --count_arr[array[i]];
    }

    // 复制回原来的数组
    for (int i = 0; i < size; ++i) {
        array[i] = output[i];
    }

    free(count_arr);
    free(output);
}

// 打印数组
void print_array(const int *array, int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

此段代码实现了计数排序的核心逻辑[^1]。首先定义了一个辅助函数`find_max()`来获取输入数组的最大值；随后，在`counting_sort()`内创建了相应的计数表，并进行了必要的处理以确保稳定性[^4]。

最后提供了测试用法如下所示：

int main() {
    int data[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(data)/sizeof(data[0]);

    printf("Original Array:\n");
    print_array(data, n);

    counting_sort(data, n);

    printf("Sorted Array:\n");
    print_array(data, n);

    return 0;
}

这段程序会先展示未排序前的数据序列，执行完计数排序后再显示已经排好序的结果[^2]。