技术讲解算法苏州科技.ppt

Kunming University of Science Technology 计数排序 作者：俞家昀 1. 引言 算法设计中主要考虑时间和空间的相互作用。 首先，并不是在所有的情况下，时间和空间都必须相互竞争，它们也可以联系起来，使得算法无论在运行时间和消耗的空间上都达到最小化。 但是，往往这种最小化很难达到，我们往往采用增大空间消耗，以保证时间最短。 Page * 计数排序 1.比较计数 2.分布计数 2.1 比较计数的数学思想 针对待排序列表中的每一个元素，算出列表中小于该元素的元素个数，并把结果记录在一张表中。这个“个数”就指出了该元素在有序列表中的位置。因此，我们可以简单的把列表的元素，复制到它在有序的新列表中的相应位置上，来对列表进行排序。这个算法称为“比较计数”。 Page * 2.2 比较计数的伪代码 算法 ComparisonCountingSort(A[1..n]) //用比较计数法对数组排序 //输入：可排序数组A[1..n] //输出：将A中元素按照升序排列的数组S[1..n] for i ←1 to n do Count [i] ←1 for i ←1 to n-1 do for j ←i+1 to n do if A[i]=A[j] Count[j] ←Count[j]+1 else Count[i] ←Count[i]+1 for i ← 1 to n do S[Count[i]] ←A[i] ruturn S 例如：A[6,3,8,9,1,4] 6 3 8 9 1 4 1 1 1 1 1 1 4 1 2 2 1 1 2 3 3 1 2 5 4 1 2 6 1 2 1 3 4 2 5 6 1 3 1 3 4 6 8 9 3.1 分布计数的数学思想 针对待排序列表中的每一个元素，如果元素的值是位于下界 L 和上界 U 之间的整数，我们就可以计算每个这样的值出现的频率，然后把它们存储在数组中。这种频率的累积和在统计中称为分布，这个方法本身也称作“分布计数”。 3.2 分布计数的伪代码 算法 DistributionCounting(A[0..n-1],L,U) //用分布计数法，对来自于有限范围整数的一个数组进行排序 //输入：数组A[0..n-1],数组中的整数位于L和U之间 （L=U） //输出：A中元素构成的非降序数组S[0..n-1] for j ←0 to U-L do D[j] ←0 //初始化频率数组 for i ←0 to n-1 do D[A[i]-L] ← D[A[i]-L] +1 //计算频率值 for j ←1 to U-L do D[j] ←D[j-1]+D[j] //重用于分布 for i ←n-1 downto 0 do j ←A[i]-L S[D[j]-1] ←A[i] D[j] ←D[j]-1 ruturn S Kunming University of Science Technology