计数排序#xff08;Counting

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

计数排序Counting

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

找出待排序数组中的最大值并创建一个统计数组count[]其长度为最大值加1。

遍历待排序数组统计每个元素出现的次数将统计结果存储在count[]数组中。

count[i]表示元素i出现的次数。

对count[]数组进行累加得到每个元素在排序后的数组中的最后一个位置。

即count[i]表示小于等于元素i的元素个数。

逆序遍历待排序数组根据count[]数组中的记录将每个元素放入temp[]数组中的正确位置。

计数排序的时间复杂度为O(nk)其中n是待排序数组的长度k是待排序数组中的最大值。

由于需要创建额外的count[]和temp[]数组所以空间复杂度为O(nk)。

需要注意的是计数排序适用于元素范围较小且非负整数的排序如果待排序数组包含负数或者小数则需要进行适当的转换或调整。

计数排序是稳定的排序算法因为相同元素的相对顺序在排序后保持不变但它不是基于比较的排序算法因此在某些情况下比其他排序算法更高效。

#include

根据count[]数组中的记录将元素放入temp[]数组的正确位置for

(int

sizeof(arr[0]);printf(排序前的数组\n);for

(int

6.逆序遍历原数组根据count[]数组中的记录将元素放入temp[]数组的正确位置。