python计数排序和基数排序算法实例 -电脑资料.docxVIP

python计数排序和基数排序算法实例-电脑资料

一、计数排序

计数排序(Countingsort)是一种稳定的排序算法算法的步骤如下：

找出待排序的数组中最大和最小的元素

统计数组中每个值为i的元素出现的次数，存入数组C的第i项

对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

当输入的元素是n个0到k之间的整数时,计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)，

python计数排序和基数排序算法实例

。当K不是很大时，这是一个很有效的线性排序算法。以下是测试代码：

复制代码代码如下:#-*-coding:utf8-*-importrandom

defjishu(data,max):

基数排序:当输入的元素是n个0到k之间的整数时(k不能太大,即max不能太大)@paramdata:需要排序的数组

@parammax:最大的数

result=[Noneforiinxrange(len(data))]#最后的结果c=[0foriinrange(max+1)]

#用数组c统计每个值=d的元素个数

fordindata:c[d]=c[d]+1

#c[i]表示data中值=i的元素个数foriinrange(1,max+1):

c[i]=c[i]+c[i-1]

#在将C中的元素倒着打印出来就是排序好的forjinxrange(len(data)-1,-1,-1):

result[c[data[j]]-1]=data[j]c[data[j]]=c[data[j]]–1

returnresult

ifname==main:#制造1000个0到100的数字

printjishu([random.randint(0,100)foriinrange(1000)],100)

二、基数排序

基数排序排序（英语：Radixsort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然

后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

以下是一个测试用例：复制代码代码如下:

#-*-coding:utf8-*-

importrandom

defjichu(data,length):

基数排lsd

@paramdata:需要排列的组合

@paramlength:最大的数据是几位

forlinxrange(length):s=[[]foriinxrange(10)]fordindata:

s[d/(10**l)%10].append(d)

data=[dfors_listinsfordins_list]returndata

ifname==main:

list=[random.randint(1,foriinxrange(99)]#制造99个数据printjichu(list,8)