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[j] > max:max=L[j]index=jtemp = LL=maxL[index]=tempprint(L)def insertSort(self,L):size = len(L)for i in range(1,size):fv = Lj = iwhile(j>=1):if fv < L[j-1]:L[j] = L[j-1]else:breakj=j-1L[j] = 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[j]>L[j+1]:temp = L[j]L[j]=L[j+1]L[j+1] = 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[index1] > L2[index2]:L.append(L2[index2])index2 = index2 + 1else:L.append(L1[index1])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 = 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 = leftj = rightmiddle = L[left]while i<=j:while L<middle and i<right:i += 1while L[j]>middle and j>left:j -= 1if i<=j: #命中一对temp = LL = L[j]L[j] = 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 = [l0,l1,l2,l3,l4,l5,l6,l7,l8,l9]return bucket#基数排序def radixSort(self,L):radix = 10base = 1bucket = self.__bucketInit()max = L[0]for 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[index].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[0]#拿到最大和最小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[i-min]):#count[i-min]表示该数字出现次数，0次地话不处理，多次的话依次插入#print("j="+str(j))L[z] = iprint(L)z+=1print(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)

运行结果: