一、算法简介
计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于待排序元素为整数且范围较小的情况。它通过统计每个元素出现的次数，然后利用次数信息将原始序列重新组合成有序序列。
计数排序的基本思想是，对待排序的元素进行计数，并建立一个长度等于最大元素值加上1的辅助数组（计数数组），用来存储每个元素出现的次数。然后根据计数数组的信息，依次将元素放回原始数组中的正确位置，以实现排序。
计数排序的具体步骤如下：
- 统计原始数组中每个元素出现的次数，存储在计数数组中。
- 对计数数组进行前缀和操作，将计数数组转化为每个元素在有序排列中的最后一个位置的索引。
- 根据计数数组的信息，依次将元素放回原始数组中的正确位置，同时更新计数数组中对应元素的值。
- 完成排序后，原始数组中的元素就按非递减顺序排列。
计数排序的时间复杂度为O(n+k)，其中n是待排序数组的长度，k是待排序数组中元素的范围。由于需要创建额外的计数数组，计数排序是一种空间换时间的排序算法。
二、算法实现
下面是计数排序的C#实现示例：
public static void CountingSort(int[] array) { int n = array.Length; // 找到最大值和最小值 int minVal = array[0]; int maxVal = array[0]; for (int i = 1; i < n; i++) { if (array[i] < minVal) { minVal = array[i]; } if (array[i] > maxVal) { maxVal = array[i]; } } // 创建计数数组并初始化为0 int[] countArray = new int[maxVal - minVal + 1]; for (int i = 0; i < n; i++) { countArray[array[i] - minVal]++; } // 计算每个元素在有序排列中的最后一个位置的索引 for (int i = 1; i < countArray.Length; i++) { countArray[i] += countArray[i - 1]; } // 创建临时数组，用于存储排序后的结果 int[] tempArray = new int[n]; // 将元素放回原始数组中的正确位置 for (int i = n - 1; i >= 0; i--) { int index = countArray[array[i] - minVal] - 1; tempArray[index] = array[i]; countArray[array[i] - minVal]--; } // 将排序好的结果复制回原始数组 for (int i = 0; i < n; i++) { array[i] = tempArray[i]; } }
调用示例：
int[] array = { 4, 2, 2, 8, 3, 3, 1 }; CountingSort(array); Console.WriteLine("排序后的数组："); foreach (int element in array) { Console.Write(element + " "); }
以上是计数排序的一个示例实现。在这个示例中，我们首先找到原始数组中的最大值和最小值，并根据二者的差值创建了一个计数数组。然后统计每个元素出现的次数，对计数数组进行前缀和操作，计算每个元素在有序排列中的最后一个位置的索引。接着，依次将元素放回原始数组中的正确位置，完成排序过程。
需要注意的是，在应用计数排序时，要确保待排序数组中的元素都是非负整数或可映射到非负整数范围内，因为计数排序的关键是统计每个元素出现的次数。如果待排序的元素不满足这个要求，就需要对其进行映射转换，才能使用计数排序算法。
