排序算法---计数排序

原创不易，转载请注明出处。欢迎点赞收藏~

计数排序（Counting Sort）是一种线性时间复杂度的排序算法，其核心思想是通过统计待排序元素的个数来确定元素的相对位置，从而实现排序。

具体的计数排序算法步骤如下： 1. 找出待排序数组中的最大值，并创建一个统计数组count[]，其长度为最大值加1。 2. 遍历待排序数组，统计每个元素出现的次数，将统计结果存储在count[]数组中。count[i]表示元素i出现的次数。 3. 对count[]数组进行累加，得到每个元素在排序后的数组中的最后一个位置。即count[i]表示小于等于元素i的元素个数。 4. 创建一个临时数组temp[]，其长度与待排序数组相同。 5. 逆序遍历待排序数组，根据count[]数组中的记录，将每个元素放入temp[]数组中的正确位置。 6. 将temp[]数组的元素复制回待排序数组，完成排序。

计数排序的时间复杂度为O(n+k)，其中n是待排序数组的长度，k是待排序数组中的最大值。由于需要创建额外的count[]和temp[]数组，所以空间复杂度为O(n+k)。

需要注意的是，计数排序适用于元素范围较小且非负整数的排序，如果待排序数组包含负数或者小数，则需要进行适当的转换或调整。计数排序是稳定的排序算法，因为相同元素的相对顺序在排序后保持不变，但它不是基于比较的排序算法，因此在某些情况下比其他排序算法更高效。

下面是一个使用C语言实现的计数排序示例：

#include <stdio.h> void counting_sort(int arr[], int n) { int max = arr[0]; // 找出最大值 for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } // 创建统计数组count[]，并初始化为0 int count[max + 1]; for (int i = 0; i <= max; i++) { count[i] = 0; } // 统计每个元素的次数 for (int i = 0; i < n; i++) { count[arr[i]]++; } // 累加count[]数组，表示小于等于元素i的元素个数 for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } // 创建临时数组temp[]，存储排好序的元素 int temp[n]; // 根据count[]数组中的记录，将元素放入temp[]数组的正确位置 for (int i = n - 1; i >= 0; i--) { temp[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // 将temp[]数组的元素复制回原数组arr[] for (int i = 0; i < n; i++) { arr[i] = temp[i]; } } int main() { int arr[] = {9, 3, 6, 1, 3, 2, 9, 0}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前的数组：\n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } counting_sort(arr, n); printf("\n排序后的数组: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } putchar('\n'); return 0; }

这段代码实现了计数排序算法。主要包括以下步骤：

1.遍历数组找出最大值，确定统计数组count[]的长度。 2.创建并初始化统计数组count[]，长度为最大值加1。 3.遍历数组，统计每个元素的出现次数，存储在count[]中。 4.累加count[]数组，表示小于等于元素i的元素个数。 5.创建临时数组temp[]，用于存储排好序的元素。 6.逆序遍历原数组，根据count[]数组中的记录，将元素放入temp[]数组的正确位置。 7.将temp[]数组的元素复制回原数组arr[]，完成排序。

运行如上代码，你可以看到以下输出：