天气预报网站怎么做,公司网站管理维护,东坑做网站,电商网站活动推广1. 简介
计数排序（counting sort）于1954年由哈罗德H西华德（Harold H. Seward）提出。计数排序是一种基于数组键值的正整数排序算法，通过对等于不同键值的数据进行计数，从而获得待排序序列的位置关系。由此，这种算法不是基于比较排序，并且比较排序的性能下限 O ( n log …1. 简介
计数排序（counting sort）于1954年由哈罗德·H·西华德（Harold H. Seward）提出。计数排序是一种基于数组键值的正整数排序算法，通过对等于不同键值的数据进行计数，从而获得待排序序列的位置关系。由此，这种算法不是基于比较排序，并且比较排序的性能下限 O ( n log n ) O{\left(n\log n \right)} O(nlogn)不适用于计数排序。计数排序的时间复杂度和空间复杂度都为 O ( n + k ) O{\left(n+k\right)} O(n+k)
计数排序与其他算法不同，需要一些前提条件：
待排序序列中每个元素的值都 ≥ 0 \ge 0 ≥0。待排序序列数组的键值都 ≥ 0 \ge 0 ≥0。知道待排序序列中的最大值 k。（不知道的情况下，则遍历待排序序列求得最大值）2. 步骤
根据最大值 k 申请一个长度为 k + 1 的数组以存储元素计数，并且全部初始化为 0。可以把这个序列叫做计数数组。申请一个和待排序序列等长的数组用以存储排序后的数据。遍历待排序序列，如果元素等于计数数组的键值，则键值的值 +1。根据计数序列的值计算演算出所有位置（索引数列）。再次遍历待排序序列将，所有数放入计数序列的指定位置。举例： 待排序序列为：
01234567891360635252得最大值为 k = 6 申请一个长度为 k + 1 的计数数组
01234560000000计数数组的键值等于待排序元素的值，遍历待排序序列得计数数组为：
01234561122022接着就是根据计数数组得元素的排序位置（不断累加计数）：
0123456计数1122022索引 0 + 1 = 1 0+{\color{red}1}={\color{red}1} 0+1=1 1 + 1 = 2 1+{\color{red}1}={\color{green}2} 1+1=2 2 + 2 = 4 2+{\color{green}2}={\color{blue}4} 2+
