什么是计数排序算法？详述计数排序算法的原理？用C语言实现计数排序算法。内附代码。

大家好，我是贤弟！

一、什么是计数排序算法？

计数排序算法是一种非比较排序算法，它的基本思想是对于给定的输入序列中的每一个元素x，确定小于x的元素个数，利用这一信息将x直接放到它在输出序列中的位置上。

二、计数排序算法的原理

计数排序算法的原理如下：

1. 找出待排序的数组中最大和最小的元素，

2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项，

3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加），

4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

三、代码示例

下面是C语言实现计数排序算法的代码：

#include #include void countingSort(int arr[], int n) { int i, j, max = arr[0], min = arr[0]; for (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 = (int *) calloc(range, sizeof(int)); for (i = 0; i < n; i++) { count[arr[i] - min]++; } for (i = 1; i < range; i++) { count[i] += count[i - 1]; } int *output = (int *) malloc(n * sizeof(int)); for (i = n - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (i = 0; i < n; i++) { arr[i] = output[i]; } free(count); free(output);}

int main() { int arr[] = {4, 2, 2, 8, 3, 3, 1}; int n = sizeof(arr) / sizeof(arr[0]); countingSort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0;}

注意：

上述代码中，我们首先找出待排序数组中的最大值和最小值，然后创建一个大小为range的计数数组count，并将每个元素出现的次数存入count数组中。

接着，我们将count数组中的元素累加，这样count[i]就表示小于等于i的元素个数。最后，我们创建一个输出数组output，并将arr数组中的元素按照count数组中的计数放入output数组中，完成排序。