计数排序、桶排序python实现

时间：2021-09-26 11:46:43

计数排序在输入n个0到k之间的整数时，时间复杂度最好情况下为O(n+k),最坏情况下为O(n+k),平均情况为O(n+k),空间复杂度为O(n+k)，计数排序是稳定的排序。

桶排序在输入N个数据有M个桶时，假设每一个桶的数据接近N/M个且桶内使用基于比較的排序，则桶排序的时间复杂度为O(N+M*N/M*log(N/M)).假设N=M时，每一个桶仅仅有一个数据，时间复杂度减少为O(N).

桶排序的时间复杂度为O(N+M),桶排序是稳定的排序

1.计数排序

计数排序介绍及C语言实如今：计数排序(链接)

def countsort(lista):

	leng=len(lista);

	c=[];

	res=[];

	for i in range(0,100):

		c.append(0);

	for i in range(0,leng):

		c[lista[i]]=c[lista[i]]+1;

		res.append(0);

	for i in range(0,100):

		c[i]=c[i-1]+c[i];        #c中此时存放的是小于或者等于i的数字的个数

	for i in range(leng-1,-1,-1):

		res[c[lista[i]]-1]=lista[i];

		c[lista[i]]=c[lista[i]]-1;

	return res;

lista=[5,4,2,5,1,7];        #计数排序測试代码

lista=countsort(lista);

print lista;

2.桶排序

桶排序介绍及C语言实如今：桶排序(链接)

class node:

	def __init__(self,k):

		self.key=k;

		self.next=None;

def bucketsort(lista):

	h=[];

	for i in range(0,10):

		h.append(node(0));

	for i in range(0,len(lista)):

		tmp=node(lista[i]);

		map=lista[i]/10;

		p=h[map];

		if p.key is 0:

			h[map].next=tmp;

			h[map].key=h[map].key+1;

		else:

			while(p.next !=None and p.next.key<=tmp.key):

				p=p.next;

			tmp.next=p.next;

			p.next=tmp;

			h[map].key=h[map].key+1;

	k=0;

	for i in range(0,10):

		q=h[i].next;

		while(q != None ):

			lista[k]=q.key;

			k=k+1;

			q=q.next;

	return lista;

lista=[1,4,23,45,97,22,10,4];     #桶排序測试代码

bucketsort(lista);

print lista;

相关文章