defquicksort(A):_quicksort(A, 0, len(A))def_quicksort(A,l,h):if l < h: pi =_partition(A, l, h)_quicksort(A, l, pi)_quicksort(A, pi+1, h)def_partition(A,l,h):# 任何 pivot 选择策略都可以,这里选择最后一个 pi = h-1# 将 pivot 交换到最后 A[pi], A[h-1]= A[h-1], A[pi] pi, p = h-1, p[h-1] i = l-1for j inrange(l, h-1):if A[j]< p: i +=1 A[i], A[j]= A[j], A[i] i +=1 A[h-1], A[i]= A[i], A[h-1]return i
快速排序快的原因在于:
它利用了 spatial locality,总是比较相邻的元素,因此很好地利用 cache
堆排序(Heap Sort)
复杂度小结
Case
Time Complexity
Space Complexity
All
归并排序(Merge Sort)
复杂度小结
Case
Time Complexity
Space Complexity
All
思路
每次将序列二等分,各部分排好序后,再合并。
defmergesort(A):_mergesort(A, 0, len(A))def_mergesort(A,l,h):# 区间内只有小于 2 个元素,直接返回,无需排序if l+1>= h:return m = (l+h)//2_mergesort(A, l, m)_mergesort(A, m, h)_merge(A, l, m, h)def_merge(A,l,m,h): tmp = [] i, j = l, mwhile i < m and j < h:if A[i]< A[j]: tmp.append(A[i]) i +=1elif A[i]> A[j]: tmp.append(A[j]) j +=1else: tmp.append(A[i]) tmp.append(A[j]) i +=1 j +=1while i < m: tmp.append(A[i]) i +=1while j < h: tmp.append(A[j]) j +=1 A[l:h]= tmp
defmergesort(A): step =1 ll =len(A)while step <= ll: h =0for h inrange(0, ll, step*2): l, m, r = h, h+step,min(ll, h+2*step) p, q = l, mwhile p < m and q < r:if A[p]< A[q]: p +=1else: tmp = A[q] A[p+1: q+1]= A[p:q] A[p]= tmp p, m, q = p+1, m+1, q+1 step *=2return A
计数排序(Counting Sort)
复杂度小结
Case
Time Complexity
Space Complexity
All
其中 n 表述序列大小,k 表示元素的范围大小
思路
统计元素所处范围内中每个元素的数量,然后从小到大遍历生成新序列即可
counting.py
defcounting_sort(A,k,fn=lambdaele: ele): ll =len(A) counting_table = [0]*kfor ele in A: counting_table[fn(ele)]+=1 position_table = counting_table count = llfor i inreversed(range(len(position_table))): count -= position_table[i] position_table[i]= count ret = [0]*ll for i, ele inenumerate(A): key =fn(ele) ret[position_table[key]]= ele position_table[key]= position_table[key]+1return ret
基数排序(Radix Sort)
复杂度小结
Case
Time Complexity
Space Complexity
All
其中,d 表示最大数的位数,k 表示元素基数大小(如二进制,k = 2;十进制,k = 10)
思路
从最小的位数开始,如十进制中的个位,每轮对所有元素的该位数进行一次计数排序。
radix_sort.py
defradix_sort(A,d,k):defele_to_key_gen(pos):defele_to_key(ele): count = d - pos -1while count >0: ele = ele // k count -=1return ele % kreturn ele_to_keyfor pos inreversed(range(d)): ele_to_key =ele_to_key_gen(pos) A =counting_sort(A, k, ele_to_key)return A