排序算法之：比较计数排序（Comparison Counting Sort） 题目描述：给定一个包含n个元素的数组，每个元素都是可比较的。使用比较计数排序算法对数组进行升序排序。该算法通过统计每个元素小于其他元素的个数来确定其正确位置。 解题过程： 算法思想： 比较计数排序的核心思想是：对于数组中的每个元素，统计有多少个其他元素比它小。如果一个元素有k个元素比它小，那么它在排序后的数组中应该位于第k+1个位置（从0开始计数）。 算法步骤： 步骤1：初始化计数数组 创建一个长度为n的计数数组count，初始值全部设为0。这个数组将记录每个元素小于其他元素的个数。 步骤2：比较并计数 使用双重循环遍历所有元素对： 外层循环i从0到n-1 内层循环j从i+1到n-1 对于每对元素(arr[ i], arr[ j ])： 如果arr[ i] > arr[ j]，则count[ i]加1（说明arr[ i]比arr[ j ]大，位置要靠后） 如果arr[ i] < arr[ j]，则count[ j]加1（说明arr[ j]比arr[ i ]大，位置要靠后） 如果相等，不需要操作（相等元素保持原顺序） 步骤3：创建结果数组 创建一个长度为n的结果数组sorted_ arr。 遍历计数数组count，对于每个索引i： 将arr[ i]放入sorted_ arr[ count[ i] ]位置 示例演示： 假设数组arr = [ 4, 2, 5, 1 ] 步骤1：初始化count = [ 0, 0, 0, 0 ] 步骤2：比较计数： 比较4和2：4>2 → count[ 0]++ → count = [ 1,0,0,0 ] 比较4和5：4<5 → count[ 2]++ → count = [ 1,0,1,0 ] 比较4和1：4>1 → count[ 0]++ → count = [ 2,0,1,0 ] 比较2和5：2<5 → count[ 2]++ → count = [ 2,0,2,0 ] 比较2和1：2>1 → count[ 1]++ → count = [ 2,1,2,0 ] 比较5和1：5>1 → count[ 2]++ → count = [ 2,1,3,0 ] 最终count = [ 2, 1, 3, 0 ] 步骤3：构建结果数组： arr[ 0]=4 → 放入位置2 → sorted_ arr[ 2 ]=4 arr[ 1]=2 → 放入位置1 → sorted_ arr[ 1 ]=2 arr[ 2]=5 → 放入位置3 → sorted_ arr[ 3 ]=5 arr[ 3]=1 → 放入位置0 → sorted_ arr[ 0 ]=1 结果：[ 1, 2, 4, 5 ] 算法分析： 时间复杂度：O(n²) - 需要n(n-1)/2次比较 空间复杂度：O(n) - 需要额外的计数数组和结果数组 稳定性：是稳定排序，相等元素保持原顺序 适用场景： 适用于数据量不大且需要稳定排序的场景，算法实现简单直观，易于理解。