常考常考高频率
1.快排（双指针）
快排，归并排序，堆排序
#快速排序O（nlogn）
def quick_sort(array, left, right):if left < right:mid = partition(array, left, right)quick_sort(array, left, mid)quick_sort(array, mid+1, right)return arraydef partition(array, left, right):pivot = array[left]while left < right:while (left <right and array[right]>= pivot):right -= 1array[left] = array[right]while (left< right and array[left] <= pivot):left += 1array[right] = array[left]array[left] = pivotreturn left
# 归并排序O（nlogn）
def merge(left, right):array = []while (len(left)>0 and len(right)>0):if left[0] < right[0]:array.append(left.pop(0))else:array.append(right.pop(0))array += leftarray += rightreturn arraydef merge_sort(array):if len(array) <= 1: #如果array只有一个元素直接退出return arraymid = len(array)//2left = merge_sort(array[:mid])right = merge_sort(array[mid:])array_new = merge(left, right)return array_new2. 第K大（快排or 堆）
力扣215.数组中的第K个最大的元素
912.排序数组
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:pivot = nums[0]small,equal,big = [],[],[]for i in nums:if i> pivot:big.append(i)elif i < pivot:small.append(i)else:equal.append(i)if len(big) >= k:return self.findKthLargest(big, k)elif len(big)< k and len(big) + len(equal)>=k:return pivotelse:return self.findKthLargest(small,k-len(big)-len(equal))
找到第K大的元素
'''快速排序'''
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def partition(nums, left, right):pivot = nums[left]while left< right:while (left< right and nums[right]>=pivot):right -= 1nums[left] = nums[right]while (left<right and nums[left] <= pivot):left += 1nums[right] = nums[left]nums[left] = pivotreturn leftdef randomPartition(nums, left, right): # 随机选择pivot，防止最坏情况nums是降序pivot_index = random.randint(left, right)nums[left], nums[pivot_index] = nums[pivot_index], nums[left]return partition(nums, left, right)def topKSplit(nums, left, right, k): #找到第k小的元素，如果是第1小，则index=0mid = randomPartition(nums, left, right)if mid == k-1:return nums[mid]elif mid < k-1:return topKSplit(nums, mid+1, right, k)else:return topKSplit(nums, left, mid-1, k)n = len(nums)return topKSplit(nums, 0, n-1, n-k+1) #第k大=第n-k+1小
堆排序？？？
'''堆排序'''
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def maxHeapify(arr, i, end):j = 2*i + 1while j <= end:if j+1 <= end and arr[j+1] > arr[j]:j += 1if arr[i] < arr[j]:arr[i], arr[j] = arr[j], arr[i]i = jj = 2*i + 1else:breakdef maxHepify(arr, i, end): # 大顶堆j = 2*i + 1 # j为i的左子节点【建堆时下标0表示堆顶】while j <= end: # 自上而下进行调整if j+1 <= end and arr[j+1] > arr[j]: # i的左右子节点分别为j和j+1j += 1 # 取两者之间的较大者if arr[i] < arr[j]: # 若i指示的元素小于其子节点中的较大者arr[i], arr[j] = arr[j], arr[i] # 交换i和j的元素，并继续往下判断i = j # 往下走：i调整为其子节点jj = 2*i + 1 # j调整为i的左子节点else: # 否则，结束调整breakn = len(nums)# 建堆【大顶堆】for i in range(n//2-1, -1, -1): # 从第一个非叶子节点n//2-1开始依次往上进行建堆的调整maxHepify(nums, i, n-1)# 排序：依次将堆顶元素（当前最大值）放置到尾部，并调整堆# k-1次重建堆（堆顶元素），或 k次交换到尾部（倒数第k个元素）for j in range(n-1, n-k-1, -1):nums[0], nums[j] = nums[j], nums[0] # 堆顶元素（当前最大值）放置到尾部jmaxHepify(nums, 0, j-1) # j-1变成尾部，并从堆顶0开始调整堆return nums[-k]