排序算法的稳定性：稳定的排序会让原本有相等键值的记录维持相对次序。
冒泡排序：
def bubble_sort(arr): for i in range(len(l)-1): for j in range(i+1,len(l)): if arr[i]>arr[j]: arr[i],arr[j] =arr[j],arr[i] return arr时间复杂度：O(n2)。稳定。
选择排序，优点在于数据移动，若某个元素位于正确的位置上，则它不会被移动。 def select_sort(arr): if not arr: return for i in range(len(arr)-1): min_ind = i for j in range(i+1,len(arr)): if arr[min_ind]>arr[j]: min_ind = j arr[i],arr[min_ind] = arr[min_ind],arr[i] return arr时间复杂度O(n2)。不稳定。
插入算法，对每个元素向前交换，即向前插入。 def insert_sort(arr): if not arr: return for i in range(1,len(arr)): while i>0: if arr[i] < arr[i-1]: arr[i-1],arr[i] = arr[i],arr[i-1] i -= 1 else: break return arr时间复杂度O(n2)。稳定。
希尔排序，引入间隔并且间隔变化的插入排序。 def shell_sort(arr): if not arr: return [] n = len(arr) gap = n//2 i = 1 while gap: for j in range(gap,n): i = j while i>0: if arr[i] < arr[i-gap]: arr[i],arr[i-gap] = arr[i-gap],arr[i] i -= gap else: break gap //= 2 return arr时间复杂度O(n2)。不稳定。
快速排序。 def quick_sort(arr,first,last): if first>=last: return n = len(arr) mid = arr[first] low,high = first,last while low<high: while low<high and arr[high]>=mid: high -= 1 arr[low] = arr[high] while low<high and arr[low]<mid: low += 1 arr[high] = arr[low] arr[low] = mid quick_sort(arr,first,low-1) quick_sort(arr,low+1,last) return arr时间复杂度O(nlogn)，T(n) = T(n/2)+O(n)。不稳定。
归并排序。 def merge_sort(arr): if len(arr)<=1: return arr mid = len(arr)>>1 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left,right) def merge(left,right): l,r = 0,0 res = [] while l<len(left) and r<len(right): if left[l]<=right[r]: res.append(left[l]) l += 1 else: res.append(right[r]) r += 1 res += left[l:] res += right[r:] return res时间复杂度O(nlogn)，T(n) = T(n/2)+O(n)。稳定。
排序算法总结。 二分查找。 #Method1 recursion def binary_search(arr,item): n = len(arr) arr = sorted(arr) if n: mid = n//2 if arr[mid] == item: return True elif arr[mid] > item: return binary_search(arr[:mid],item) else: return binary_search(arr[mid+1:],item) return False #iteration def binary_search(arr,item): if not arr: return False arr = sorted(arr) l, r = 0, len(arr)-1 while l<=r: mid = (l+r)>>1 if arr[mid] == item: return True elif arr[mid]<item: l = mid+1 else: r = mid-1 return False时间复杂度O(logn)。
