企业网站颜色,wordpress aike主题,阳江吧,如何做网站活动原创不易#xff0c;转载请注明出处。欢迎点赞收藏~ 计数排序#xff08;Counting Sort#xff09;是一种线性时间复杂度的排序算法#xff0c;其核心思想是通过统计待排序元素的个数来确定元素的相对位置#xff0c;从而实现排序。
具体的计数排序算法步骤如下#xff… 原创不易转载请注明出处。欢迎点赞收藏~ 计数排序Counting Sort是一种线性时间复杂度的排序算法其核心思想是通过统计待排序元素的个数来确定元素的相对位置从而实现排序。
具体的计数排序算法步骤如下 1. 找出待排序数组中的最大值并创建一个统计数组count[]其长度为最大值加1。 2. 遍历待排序数组统计每个元素出现的次数将统计结果存储在count[]数组中。count[i]表示元素i出现的次数。 3. 对count[]数组进行累加得到每个元素在排序后的数组中的最后一个位置。即count[i]表示小于等于元素i的元素个数。 4. 创建一个临时数组temp[]其长度与待排序数组相同。 5. 逆序遍历待排序数组根据count[]数组中的记录将每个元素放入temp[]数组中的正确位置。 6. 将temp[]数组的元素复制回待排序数组完成排序。
计数排序的时间复杂度为O(nk)其中n是待排序数组的长度k是待排序数组中的最大值。由于需要创建额外的count[]和temp[]数组所以空间复杂度为O(nk)。
需要注意的是计数排序适用于元素范围较小且非负整数的排序如果待排序数组包含负数或者小数则需要进行适当的转换或调整。计数排序是稳定的排序算法因为相同元素的相对顺序在排序后保持不变但它不是基于比较的排序算法因此在某些情况下比其他排序算法更高效。 下面是一个使用C语言实现的计数排序示例
#include stdio.hvoid 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[]并初始化为0int 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[]完成排序。
运行如上代码你可以看到以下输出
