Python笔记——排序算法的实现
排序算法，目前只实现了七种，后续慢慢会补上~~各位多指教分别为：
1. 选择排序
2. 插入排序
3. 冒泡排序
4. 归并排序
5. 快速排序
6. 基数排序
7.计数排序
另外还有希尔，堆，桶排序，以及各种算法的改进版本，需要去处理下
直接贴代码
# file :sort.pyimport mathclass sort:def selectSort(self,L):size = len(L)for i in range(0,size):max=Lindex = ifor j in range(i,size):if L > max:max=Lindex=jtemp = LL=maxL=tempprint(L)def insertSort(self,L):size = len(L)for i in range(1,size):fv = Lj = iwhile(j>=1):if fv < L:L = Lelse:breakj=j-1L = fvprint(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>L:temp = LL=LL = tempprint(L)def merge(self,L1,L2):L=[]index1 = 0index2 = 0size1 = len(L1)size2 = len(L2)top = min(size1,size2)while(index1!=size1 and index2!=size2 ):if L1 > L2:L.append(L2)index2 = index2 + 1else:L.append(L1)index1 = index1 + 1if index1 < size1:for i in range(index1,size1):L.append(L1)if index2 < size2:for i in range(index2,size2):L.append(L2)return Ldef mergeInL(self,L,first,mid,last):tempa = []tempb = []for i in range(first,mid+1):tempa.append(L)for i in range(mid+1,last+1):tempb.append(L)tempc = self.merge(tempa,tempb)index = 0for i in range(first,last+1):L = tempcindex += 1#我错了。。。本来两个方法，写着写着变三个方法，改天再改def mergeSort(self,L,first,last):#print("1first = %dlast = %d" %(first,last))if first < last:#print("2first = %dlast = %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 = leftj = rightmiddle = Lwhile i<=j:while L<middle and i<right:i += 1while L>middle and j>left:j -= 1if i<=j: #命中一对temp = LL = LL = tempi += 1j += 1if left<j:self.quickSort(L,left,j)if right > i:self.quickSort(L,i,right)def __bucketInit(self):l0 = []l1 = []l2 = []l3 = []l4 = []l5 = []l6 = []l7 = []l8 = []l9 = []bucket = return bucket#基数排序def radixSort(self,L):radix = 10base = 1bucket = self.__bucketInit()max = Lfor i in L:if i > max:max = iwhile math.trunc((max%radix)/base) > 0:#放到桶里for i in L:index = math.trunc((i%radix)/base)bucket.append(i)#重新整理回LL = []for i in bucket:L.extend(i)bucket = self.__bucketInit()print(L)#下一轮循环取下一位radix *= 10base *=10return L#计数排序def countSort(self,L):size = len(L)min = max = L#拿到最大和最小for i in L:if i<min:min = iif 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-min ] +=1z = 0print("min = %d and max = %d"%(min,max))for i in range(min,max+1):#print("i="+str(i))for j in range(0,count):#count表示该数字出现次数，0次地话不处理，多次的话依次插入#print("j="+str(j))L = iprint(L)z+=1print(L)a = sort()l = print('原始数组')print(l)print('选择排序')a.selectSort(l)l2 = print('插入排序')a.insertSort(l2)print('冒泡排序')l3 = a.bubbleSort(l3)print('列表归并算法 没有问题')la = lb = print(a.merge(la,lb))print('归并排序')lm = a.mergeSort(lm,0,5)print(lm)print('快速排序')lq = a.quickSort(lq,0,5)print(lq)print('基数排序')lr = print(lr)a.radixSort(lr)print("计数排序")lz = a.countSort(lz)
运行结果:
页:
[1]