python手写计数排序.zip

计数排序是一种非基于比较的排序算法，它适用于待排序的元素是整数的情况。它的基本思想是通过统计每个整数出现的次数，然后利用这些信息来直接确定每个元素在输出数组中的位置。这种排序方法在适当的情况下可以实现线性时间复杂度，即O(n)，其中n是待排序元素的数量。在Python中实现计数排序，我们需要理解以下几个关键步骤： 1. **分析范围**：我们需要知道输入数据的最小值和最大值，这将决定计数数组的大小。计数数组的长度通常设置为最大值与最小值之差加1。 2. **初始化计数数组**：创建一个大小为上述范围的计数数组，并将其所有元素初始化为0。这个数组的每个索引代表一个可能的整数值。 3. **计数过程**：遍历输入数组，对于每个元素，将其值作为计数数组的索引，将该索引处的计数加一。这样，计数数组记录了每个整数出现的次数。 4. **累加计数**：从计数数组的第二个元素开始，将每个元素的值加上前一个元素的值。这样，每个索引处的值就表示小于或等于该索引对应整数的所有元素的总数。 5. **构造输出数组**：从最小值开始，遍历计数数组。对于每个索引，将当前计数作为输出数组的元素值，并将计数减一。这个过程会按顺序填充输出数组。 6. **返回结果**：输出数组现在包含了排序后的元素，可以替换原来的输入数组或者直接返回。 在Python中实现这个算法，可以使用以下代码示例： ```python def counting_sort(arr): min_val = min(arr) max_val = max(arr) count_arr = [0] * (max_val - min_val + 1) # 计数 for num in arr: count_arr[num - min_val] += 1 # 累加计数 for i in range(1, len(count_arr)): count_arr[i] += count_arr[i - 1] # 构造输出数组 sorted_arr = [0] * len(arr) for num in arr: sorted_arr[count_arr[num - min_val] - 1] = num count_arr[num - min_val] -= 1 return sorted_arr ``` 请注意，计数排序不是稳定的排序算法，也就是说相等的元素可能会改变它们原有的相对顺序。如果需要保持原有顺序，可以使用其他方法，如插入排序。此外，虽然计数排序在处理大量整数时效率很高，但如果数据范围过大，它可能会消耗大量内存。因此，选择排序算法时应考虑数据的特性和需求。