一，堆排序，可以用来解决优先队列，topk等问题
class Solution: def sortArray(self, nums: List[int]) -> List[int]: def heapsort(nums): len_nums = len(nums) # 建堆过程，也可以理解为向上调整的过程 for i in range(len_nums//2-1, -1, -1): adjust_heap(nums, i, len_nums) # 向下调整的过程 for j in range(len_nums-1, 0, -1): nums[0], nums[j] = nums[j], nums[0] adjust_heap(nums, 0, j) def adjust_heap(target_list, target_i, target_len): # 获取左孩子结点索引 k = 2*target_i + 1 tmp = nums[target_i] while k < target_len: # 如果右孩子大，则变到右孩子处，保证最后放到i位置的是三者最大 if k+1 < target_len and nums[k+1] > nums[k]: k += 1 if tmp <target_list[k]: target_list[target_i] = target_list[k] target_i = k else: break k = 2*k +1 target_list[target_i] = tmp heapsort(nums) return nums二，归并排序 = 归并排序左半边+归并排序右半边+合并两边
class Solution: def sortArray(self, nums: List[int]) -> List[int]: def mergesort(nums): len_nums = len(nums) if len_nums <= 1: return nums mid = len_nums//2 A = mergesort(nums[:mid]) B = mergesort(nums[mid:]) return merge(A, B) def merge(A, B): C = [] while A and B: if A[0] < B[0]: C.append(A.pop(0)) else: C.append(B.pop(0)) while A: C.append(A.pop(0)) while B: C.append(B.pop(0)) return C return mergesort(nums)三，快速排序 = partition分割两边 + 快速排序左半边 + 快速排序右半边
partition思路，设置“小于等于区域”，初始时设置此区域指针i为low-1，基准值为high上的元素，遍历low到high索引上的值，遍历指针j对应的元素小于等于基准值时，区域指针加1，然后交换二者，否则继续遍历。
class Solution: def sortArray(self, nums: List[int]) -> List[int]: def partition(nums, low, high): i = low - 1 pivot = nums[high] for j in range(low, high+1): if nums[j] <= pivot: i += 1 nums[i], nums[j] = nums[j], nums[i] return i def quicksort(nums, low, high): if low < high: pi = partition(nums, low, high) quicksort(nums, low, pi-1) quicksort(nums, pi+1, high) len_nums = len(nums) if len_nums <= 1: return nums quicksort(nums, 0, len(nums)-1) return nums
四，随机快速排序，每次基准值由random决定，摇出随机索引后与最后一个元素交换
class Solution: def sortArray(self, nums: List[int]) -> List[int]: def partition(nums, low, high, pivot): l = low - 1 r = high + 1 h = low while h < r: if nums[h] < pivot: l += 1 nums[l], nums[h] = nums[h], nums[l] h += 1 elif nums[h] == pivot: h += 1 else: r -= 1 nums[r], nums[h] = nums[h], nums[r] return l+1,r-1 def quicksort(nums, low, high): if low < high: pivot = random.randint(low,high) pi_l, pi_r = partition(nums, low, high, nums[pivot]) quicksort(nums, low, pi_l-1) quicksort(nums, pi_r+1, high) len_nums = len(nums) if len_nums <= 1: return nums quicksort(nums, 0, len(nums)-1) return nums
