编程分析 计算机软件及应用 IT计算机 专业资料.doc

编程分析_计算机软件及应用_IT计算机_专业资料.doc:..算法实践 (radixsort)是在一种按位稳定排序的基础上对一组多位的数字进行按大小排列。原本是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地”程序化”以检查每一迭卡片屮的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在虽上面,第二个位置穿孔的其次,等等。对十进制数字来说,每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片3294576578394367203553367829553657572039排序器一次只能查看一个列,耍对n张片上的d位数进行排序就要有个排序算法。基数排序是首先按最低有效位数字进行排序,以解决卡片排序问题。同样,把各堆卡片收集成一迭,其中0号盒子中的在1号盒子中的前面,后者乂在2号盒子中的前面,等等。然后对整个一迭卡片按次重要位排序,并把结果同样地合并起來。重复这个过程,直到対所有的d位数字都进行了排序。在选择稳定的位排序方法上,我们可以选择计数排序(),因为在十进制中每一位都是从0到9,很容易得到计数排序是稳定的算法(Stablesort)。(A,B,k,n,r)fori:1tondoD[i]:0Fetchbit(A,D,r,n)fori:1tokdoC[i]:0fori:1tondoB[i]:0fori:1tokdoC[i]:0fori:1tondoC[D[i]]:C[D[i]]+lfori:1tokdoC[i]:C[i]+C[i-l]fori:ndownto1doB[C[D[i]]-l]:A[i]C[D[i]]:C[D[i]]-lRadix_sort(A,B,d,n)fori:1tonC[i]:0fori:1tonC[i]:A[i]fori:1todCounting_sort(C,B»10,n,i)forj:1tonC[j]:BU]Fetch_bit(A,B,r,n)fori:1tondoB[j]:A[j]/(10Ar))%•给定n个d位数,毎一个数为可以取k个可能值,基数排序能在0(cl(n-^k))吋间内正确对这些数进行排序。•给定n个b位数,和任意整数rWb,基数排序能在0((5/厂)(/7+2J)时间内正确对这些数进行排序。•基数排序是否要比基于比较的排序算法(比如快速排序)更好呢?如果根据常见的情况有b=0(lgn),并选择r^lgn,则基数排序的运行时间为0(n),这看上去要比快速排序的平均情况时间O(nlgn)更好些。然而,在这两个时间中隐含在O记号中的常数因了是不同的。对于要处理的n个关键字,尽管基数排序执行的遍数可能耍比快速排序耍少,但每一遍所需的时间都要长得多。哪一个排序算法更好取决于底层机器的实现特性(例如,快速排序通常可以比基数排序更为有效的利用硬件缓存),同吋还取决于输入的数据。此外,利用计数排序作为中间稳定排序的基数排序不是原地排序,而很多O(nlgn)时间的比较排序算法则可以做到原地排序。