成品网站货源,网站产品标签文章标签怎么做的,公司网站建设制作价格,三种人不易感染新冠背景
1954年由 Harold H. Seward 提出
基本思想#xff1a;
假设#xff1a;计数排序假设n个输入元素中的每一个都是介于0到k之间的整数
举例#xff1a;10 个年龄不同的人#xff0c;统计出有 8 个人的年龄比 A 小#xff0c;那 A 的年龄就排在第 9 位,用这个方法可以…背景
1954年由 Harold H. Seward 提出
基本思想
假设计数排序假设n个输入元素中的每一个都是介于0到k之间的整数
举例10 个年龄不同的人统计出有 8 个人的年龄比 A 小那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序
年龄有重复时需要特殊处理保证稳定性 算法最后一步
优势在于在对一定范围内的整数排序时它的复杂度为Ο(nk)其中k是整数的范围快于任何比较排序算法
当然这是一种牺牲空间换取时间的做法而且当O(k)O(n*log(n))的时候其效率反而不如基于比较的排序
算法基本步骤
1找出待排序的数组中最大和最小的元素
2统计数组中每个值为i的元素出现的次数存入数组C的第i项
3对所有的计数累加从C中的第一个元素开始每一项和前一项相加
4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
计数排序伪代码
正常的思路
COUNT—SORT(A,B,k)
let C[0..k]be a new array
for i0 to k C[i]0
for j1 to A.length C[A[j]]C[A[j]]1
//C[i]now contains the number of elements equal to i
for i1 to k C[i]C[i]C[i-1]
//C[i] now contains the number of elements less than or equal to i
//在这里最终得出的C有这样的规律,A[j]最终应该放在
//下标为C[A[j]-1]1~C[A[j]]的位置
for jA.length downto 1
//为了保持稳定性这里从后面开始遍历了
//如果换成for 1 downto jA.length,那么元素相等的地方刚好反过来B[C[A[j]]]A[j]C[A[j]]C[A[j]]-1
需要注意的是k为A中的最大值-(A中的最小值-1)
另一种思路
如果第13行我非得从1开始呢但又想保持稳定性呢该如何办
我们记得
在这里最终得出的C有这样的规律,A[j]最终应该放在下标为C[A[j]-1]1~C[A[j]]的位置
COUNT—SORT(A,B,k)
let C[0..k]be a new array
for i0 to k C[i]0
for j1 to A.length C[A[j]]C[A[j]]1
for i1 to k C[i]C[i]C[i-1]
//这里需要单独处理一下需要C[-1]0
//当然下标不可能为负数我们可以让下标整体都1就可以解决问题
//这里为了方便与上面思路对照直接认为C[-1]0是允许的
C[-1]0
for j1 downto A.lengthB[C[A[j]-1]1]A[j]C[A[j]-1]C[A[j]-1]1
//这个思路也是稳定的
计数排序举例(正常思路) 循环1 循环2 循环3 循环4 运行时间
