#coding=utf-8# file :sort.pyimport mathclass sort: def selectSort(self,L): size = len(L) for i in range(0,size): max=L[i] index = i for j in range(i,size): if L[j] > max: max=L[j] index=j temp = L[i] L[i]=max L[index]=temp print(L) def insertSort(self,L): size = len(L) for i in range(1,size): fv = L[i] j = i while(j>=1): if fv < L[j-1]: L[j] = L[j-1] else: break j=j-1 L[j] = fv print(L) def bubbleSort(self,L): size = len(L) for i in range(size-1,-1,-1): for j in range(0,i-1):#这里需要注意下，重新看下是否符合，感觉怪怪的 if L[j]>L[j+1]: temp = L[j] L[j]=L[j+1] L[j+1] = temp print(L) def merge(self,L1,L2): L=[] index1 = 0 index2 = 0 size1 = len(L1) size2 = len(L2) top = min(size1,size2) while(index1!=size1 and index2!=size2 ): if L1[index1] > L2[index2]: L.append(L2[index2]) index2 = index2 + 1 else: L.append(L1[index1]) index1 = index1 + 1 if index1 < size1: for i in range(index1,size1): L.append(L1[i]) if index2 < size2: for i in range(index2,size2): L.append(L2[i]) return L def mergeInL(self,L,first,mid,last): tempa = [] tempb = [] for i in range(first,mid+1): tempa.append(L[i]) for i in range(mid+1,last+1): tempb.append(L[i]) tempc = self.merge(tempa,tempb) index = 0 for i in range(first,last+1): L[i] = tempc[index] index += 1 #我错了。。。本来两个方法，写着写着变三个方法，改天再改 def mergeSort(self,L,first,last): #print("1first = %d last = %d" %(first,last)) if first < last: #print("2first = %d last = %d"%(first,last)) mid = math.trunc((first+last)/2) #必须拿到整数,晕死 self.mergeSort(L,first,mid) self.mergeSort(L,mid+1,last) self.mergeInL(L,first,mid,last) #代码简洁效率高~~改天实现改进版的 def quickSort(self,L,left,right): i = left j = right middle = L[left] while i<=j: while L[i] middle and j>left: j -= 1 if i<=j: #命中一对 temp = L[i] L[i] = L[j] L[j] = temp i += 1 j += 1 if left i: self.quickSort(L,i,right) def __bucketInit(self): l0 = [] l1 = [] l2 = [] l3 = [] l4 = [] l5 = [] l6 = [] l7 = [] l8 = [] l9 = [] bucket = [l0,l1,l2,l3,l4,l5,l6,l7,l8,l9] return bucket #基数排序 def radixSort(self,L): radix = 10 base = 1 bucket = self.__bucketInit() max = L[0] for i in L: if i > max: max = i while math.trunc((max%radix)/base) > 0: #放到桶里 for i in L: index = math.trunc((i%radix)/base) bucket[index].append(i) #重新整理回L L = [] for i in bucket: L.extend(i) bucket = self.__bucketInit() print(L) #下一轮循环取下一位 radix *= 10 base *=10 return L #计数排序 def countSort(self,L): size = len(L) min = max = L[0] #拿到最大和最小 for i in L: if i max: max = i #得到数字的区间 bound = max - min +1 #初始化计数数组 count =[] for i in range(0,bound): count.append(0) #统计每个数出现的次数，放到count中 for i in range(0,size): count[ L[i]-min ] +=1 z = 0 print("min = %d and max = %d"%(min,max)) for i in range(min,max+1): #print("i="+str(i)) for j in range(0,count[i-min]):#count[i-min]表示该数字出现次数，0次地话不处理，多次的话依次插入 #print("j="+str(j)) L[z] = i print(L) z+=1 print(L)a = sort()l = [3,2,5,7,1,9]print('原始数组')print(l)print('选择排序')a.selectSort(l)l2 = [3,2,5,7,1,9]print('插入排序')a.insertSort(l2)print('冒泡排序')l3 = [3,2,5,7,1,9]a.bubbleSort(l3)print('列表归并算法 没有问题')la = [1,3,5,7,9,11]lb = [2,4,6,8]print(a.merge(la,lb))print('归并排序')lm = [3,2,5,7,1,9]a.mergeSort(lm,0,5)print(lm)print('快速排序')lq = [3,2,5,7,1,9]a.quickSort(lq,0,5)print(lq)print('基数排序')lr = [3,20,5,713,1,9]print(lr)a.radixSort(lr)print("计数排序")lz = [3,2,5,7,1,9]a.countSort(lz) 运行结果：
/usr/bin/python2.7 ~/PycharmProjects/py2/sort.py原始数组[3, 2, 5, 7, 1, 9]选择排序[9, 2, 5, 7, 1, 3][9, 7, 5, 2, 1, 3][9, 7, 5, 2, 1, 3][9, 7, 5, 3, 1, 2][9, 7, 5, 3, 2, 1][9, 7, 5, 3, 2, 1]插入排序[2, 3, 5, 7, 1, 9][2, 3, 5, 7, 1, 9][2, 3, 5, 7, 1, 9][1, 2, 3, 5, 7, 9][1, 2, 3, 5, 7, 9]冒泡排序[2, 3, 5, 1, 7, 9][2, 3, 1, 5, 7, 9][2, 1, 3, 5, 7, 9][1, 2, 3, 5, 7, 9][1, 2, 3, 5, 7, 9][1, 2, 3, 5, 7, 9]列表归并算法 没有问题[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]归并排序[1, 2, 3, 5, 7, 9]快速排序[1, 2, 3, 5, 7, 9]基数排序[3, 20, 5, 713, 1, 9][20, 1, 3, 713, 5, 9][1, 3, 5, 9, 713, 20][1, 3, 5, 9, 20, 713]计数排序min = 1 and max = 9[1, 2, 5, 7, 1, 9][1, 2, 5, 7, 1, 9][1, 2, 3, 7, 1, 9][1, 2, 3, 5, 1, 9][1, 2, 3, 5, 7, 9][1, 2, 3, 5, 7, 9][1, 2, 3, 5, 7, 9]Process finished with exit code 0