sort.md

排序

常考排序

快速排序

importrandomdefpartition(nums, left, right): ifleft>=right: returnpivot_idx=random.randint(left, right) pivot=nums[pivot_idx] nums[right], nums[pivot_idx] =nums[pivot_idx], nums[right] partition_idx=leftforiinrange(left, right): ifnums[i] <pivot: nums[partition_idx], nums[i] =nums[i], nums[partition_idx] partition_idx+=1nums[right], nums[partition_idx] =nums[partition_idx], nums[right] partition(nums, partition_idx+1, right) partition(nums, left, partition_idx-1) returndefquicksort(A): partition(A, 0, len(A) -1) returnAif__name__=='__main__': a= [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10] print(a) print(quicksort(a))

归并排序

defmerge(A, B): C= [] i, j=0, 0whilei<len(A) andj<len(B): ifA[i] <=B[j]: C.append(A[i]) i+=1else: C.append(B[j]) j+=1ifi<len(A): C+=A[i:] ifj<len(B): C+=B[j:] returnCdefmergsort(A): n=len(A) ifn<2: returnA[:] left=mergsort(A[:n//2]) right=mergsort(A[n//2:]) returnmerge(left, right) if__name__=='__main__': a= [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10] print(a) print(mergsort(a))

堆排序

用数组表示的完美二叉树 complete binary tree

完美二叉树 VS 其他二叉树

动画展示

核心代码

defheap_adjust(A, start=0, end=None): ifendisNone: end=len(A) whilestartisnotNoneandstart<end//2: l, r=start*2+1, start*2+2swap=NoneifA[l] >A[start]: swap=lifr<endandA[r] >A[start] and (swapisNoneorA[r] >A[l]): swap=rifswapisnotNone: A[start], A[swap] =A[swap], A[start] start=swapreturndefheapsort(A): # construct max heapn=len(A) foriinrange(n//2-1, -1, -1): heap_adjust(A, i) # sortforiinrange(n-1, 0, -1): A[0], A[i] =A[i], A[0] heap_adjust(A, end=i) returnA# testif__name__=='__main__': a= [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10] print(a) print(heapsort(a))

题目

kth-largest-element-in-an-array

• 思路 1: sort 后取第 k 个，最简单直接，复杂度 O(N log N) 代码略

• 思路 2: 使用最小堆，复杂度 O(N log k)

classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: # note that in practice there is a more efficient python build-in function heapq.nlargest(k, nums)min_heap= [] fornuminnums: iflen(min_heap) <k: heapq.heappush(min_heap, num) else: ifnum>min_heap[0]: heapq.heappushpop(min_heap, num) returnmin_heap[0]

• 思路 3: Quick select，方式类似于快排，每次 partition 后检查 pivot 是否为第 k 个元素，如果是则直接返回，如果比 k 大，则继续 partition 小于 pivot 的元素，如果比 k 小则继续 partition 大于 pivot 的元素。相较于快排，quick select 每次只需 partition 一侧，因此平均复杂度为 O(N)。

classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: k-=1# 0-based indexdefpartition(left, right): pivot_idx=random.randint(left, right) pivot=nums[pivot_idx] nums[right], nums[pivot_idx] =nums[pivot_idx], nums[right] partition_idx=leftforiinrange(left, right): ifnums[i] >pivot: nums[partition_idx], nums[i] =nums[i], nums[partition_idx] partition_idx+=1nums[right], nums[partition_idx] =nums[partition_idx], nums[right] returnpartition_idxleft, right=0, len(nums) -1whileTrue: partition_idx=partition(left, right) ifpartition_idx==k: returnnums[k] elifpartition_idx<k: left=partition_idx+1else: right=partition_idx-1

参考

十大经典排序

二叉堆

练习

• 手写快排、归并、堆排序