新手入门C语言实现计数排序算法

计数排序是一种非基于比较的整数排序算法，特别适合于数据范围较小且都是正整数的情况。下面是新手入门C语言实现计数排序的基本步骤：

1. **确定最大值**：遍历待排序数组找出其中的最大元素，用于创建计数数组。

2. **创建计数数组**：计数数组的长度与最大值+1相同，每个元素初始化为0。对于输入数组中的每个元素，计数数组对应位置的值加一。

3. **累计计数**：从计数数组的第一个元素开始，对每个位置的值累加，得到每个元素实际的位置。

4. **填充结果**：将原数组中的元素按照计数数组计算出的新位置复制到新的有序数组中。

5. **输出结果**：最后的结果数组就是按顺序排列后的原始数组。

下面是一个简单的C语言实现示例：

#include <stdio.h>

void countingSort(int arr[], int n) {
    // Step 1: Find maximum value in the array
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
    }

    // Step 2: Create count array
    int count[max + 1];

    // Initialize count array to all zeros
    for (int i = 0; i <= max; i++)
        count[i] = 0;

    // Step 3: Count elements
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // Step 4: Cumulative count and build result array
    int sorted[n];
    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            sorted[index++] = i;
            count[i]--;
        }
    }

    // Step 5: Copy back the sorted elements into original array
    for (int i = 0; i < n; i++)
        arr[i] = sorted[i];
}

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

    countingSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}