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

参考

十大经典排序

二叉堆

练习

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