冒泡、选择、插入、归并、快排、计数、基数排序算法的python实现

######## 基于比较的排序方法 ################# 1. Bubble Sort #########def BubbleSort(a): #average:O(N^2), best:O(N)#length = len(a)flag = True #数组有序时，跳出循环、不再冒泡for i in range(length-1): #length-1次flag = Falsefor j in range(length-1-i):if a[j] > a[j+1]:flag = Truea[j],a[j+1] = a[j+1],a[j]if not flag: breakreturn a######### 2. Selection Sort #########def SelectionSort(a):#O(N^2)length = len(a)for i in range(length-1):min = i,a[i]for j in range(i+1, length):if a[j] < min[1]:min = j,a[j]a[i],a[min[0]] = a[min[0]],a[i]return a######### 3. Insertion Sort #########def InsertionSort(a):#O(N^2)length = len(a)for i in range(1,length):for j in range(i-1,-1,-1):if a[j]>a[j+1]:#有点像反过来的冒泡排序a[j+1],a[j]=a[j],a[j+1]return a######### 4. Merge Sort #########def MergeSort(a):#O(NlogN)if len(a) <= 1: return amid = len(a)//2left = MergeSort(a[:mid])#必须是mid，不能是mid+1，否则len(a)=2时会陷入死循环right = MergeSort(a[mid:])return Merge(left, right)def Merge(a,b):res = []p1, p2 = 0,0m1,m2 = len(a),len(b)while p1= end: returnnewPivot = partition(a,start,end)QuickSort(a,start,newPivot)QuickSort(a,newPivot+1,end)return adef partition(a,start=0,end=None):#[start,end),返回排序后pivot的位置，且pivot左小右大end = len(a) if end is None else endpivot = a[start]partition = start + 1for i in range(start+1,end):if a[i]= end: returnnewPivot = random_partition(a,start,end)RandomQuickSort(a,start,newPivot)RandomQuickSort(a,newPivot+1,end)return adef random_partition(a,start=0,end=None):#[start,end),返回排序后pivot的位置，且pivot左小右大end = len(a) if end is None else end##小区别##newstart = random.randint(start,end-1)a[start], a[newstart] = a[newstart], a[start]##pivot = a[start]partition = start + 1for i in range(start+1,end):if a[i] O(N)maxi = max(a)digits = len(str(maxi)) #记录最大值的位数，即为接下来的排序轮数for digit in range(digits):bucket = [[] for _ in range(10)] #记录0~9的10个桶for i in a:temp = digitK(i,digit)bucket[temp].append(i)a = [j for i in bucket for j in i]return adef digitK(num,k):if k==0: return num%10return digitK(num//10, k-1) 【冒泡、选择、插入、归并、快排、计数、基数排序算法的python实现】

冒泡、选择、插入、归并、快排、计数、基数 排序算法的python实现

冒泡、选择、插入、归并、快排、计数、基数排序算法的python实现