Python笔记——排序算法的实现

排序算法，目前只实现了七种，后续慢慢会补上~~各位多指教

分别为：

1. 选择排序

2. 插入排序

3. 冒泡排序

4. 归并排序

5. 快速排序

6. 基数排序

7.计数排序

另外还有希尔，堆，桶排序，以及各种算法的改进版本，需要去处理下

直接贴代码

# file :sort.py import math class 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 i<right: i += 1 while L[j]>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<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 = 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<min: min = i 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)

运行结果: