classCocktailSort(Base):defexecute(self,L: List[int]) -> List[int]: flag =Truefor i inrange(len(L) //2):if flag: flag =Falsefor j inrange(i, len(L) - i -1):if L[j]> L[j+1]: L[j], L[j+1]= L[j+1], L[j] flag =Truefor j inrange(len(L) -1- i, i, -1):if L[j]< L[j-1]: L[j], L[j-1]= L[j-1], L[j] flag =Trueelse:breakreturn L
分析
时间复杂度:鸡尾酒排序的效率还是很低的,两层循环,时间复杂度为 O(n^2) 。
空间复杂度:由于只需要几个临时变量,所以空间复杂度为 O(1) 。
插入排序
classInsertionSort(Base):defexecute(self,L: List[int]) -> List[int]:for p inrange(1, self.length): tmp = L[p] i = pwhile i >0and L[i-1]> tmp: L[i]= L[i-1] i = i-1 L[i]= tmpreturn L
由于用来计数的数组 C 的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。
classCountingSort(Base):defexecute(self,L: List[int]) -> List[int]: n =len(L) max_value =max(L) min_value =min(L) count = [0] * (max_value - min_value +2) # 优化count数组空间for i in L: count[i]+=1 sort_L = []for j inrange(len(count)):if count[j]!=0:for y inrange(count[j]): sort_L.append(j)return sort_L
classBucketSort(Base):defexecute(self,L: List[int]) -> List[int]: bucket_length =max(L)//10+1 buckets = [[] for i inrange(0, bucket_length)]for i in L: buckets[i //10].append(i)for i in buckets: quicksort =QuickSort(len(i)) i = quicksort.execute(i) sort_L = []for i in buckets:ifisinstance(i, list):for j in i: sort_L.append(j)else: sort_L.append(i)return sort_L
快速排序
挑选基准值:从数列中挑出一个元素,称为“基准”(pivot),
分割:所有比基准值小的元素放在基准值的左边,所有比基准值大的元素放在基准值的右边,分割成两个子序列
递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
classQuickSort(Base):defexecute(self,L: List[int]) -> List[int]: length =len(L)if length <=1:return L self.quicksort(L, 0, length -1)return Ldefpartition(self,L: List[int],left:int,right:int) ->int: key = leftwhile left < right:while left < right and L[right]>= L[key]: right -=1while left < right and L[left]<= L[key]: left +=1 L[left], L[right]= L[right], L[left] L[left], L[key]= L[key], L[left]return leftdefquicksort(self,L: List[int],left:int,right:int):if left >= right:return mid = self.partition(L, left, right) self.quicksort(L, left, mid -1) self.quicksort(L, mid +1, right)
归并排序
分而治之
(分)将一个序列从中间位置分成两个序列
继续将这两个子序列按照第一步继续二分下去
直到所有子序列的长度都为1(终止)
(治)两两合并成一个有序序列
classMergeSort(Base):defexecute(self,L: List[int]) -> List[int]: return self.merge_sort(L)defmerge(self,a: List[int],b: List[int]) -> List[int]: merged = [] i, j =0,0while i <len(a)and j <len(b):if a[i]<= b[j]: merged.append(a[i]) i +=1else: merged.append(b[j]) j +=1 merged.extend(a[i:]) merged.extend(b[j:])return mergeddefmerge_sort(self,L: List[int]) -> List[int]:iflen(L)<=1:return L mid =len(L)//2 a = self.merge_sort(L[:mid]) b = self.merge_sort(L[mid:])return self.merge(a, b)