2024.5.25AcWing刷题记录-排序篇
一、786. 第k个数 - AcWing题库
三路快速排序
import random
def func(nums, start, end):if start >= end:return idx = random.randint(start, end)base = nums[idx]i, j, m = start, start, end + 1while j < m:if nums[j] < base:nums[i], nums[j] = nums[j], nums[i]i += 1j += 1elif nums[j] > base:nums[j], nums[m - 1] = nums[m - 1], nums[j]m -= 1else:j += 1func(nums, start, i - 1)func(nums, m, end)n, k = map(int, input().split())
nums = list(map(int, input().split()))
func(nums, 0, len(nums) - 1)
print(nums[k - 1])二、787. 归并排序 - AcWing题库
递归归并排序
def merge_sort(nums):n = len(nums)if n <= 1:return numsmid = n // 2left = merge_sort(nums[:mid])right = merge_sort(nums[mid:])res = []i, j = 0, 0# 左右列表长度while i < mid and j < n - mid:if right[j] < left[i]:res.append(right[j])j += 1else:res.append(left[i])i += 1# 将剩下的添加到末尾res += left[i:]res += right[j:]return res
n = int(input())
nums = list(map(int, input().split()))
nums = merge_sort(nums)
for x in nums:print(x, end = ' ')三、788. 逆序对的数量 - AcWing题库
归并排序时计数
# 使用归并排序时计数
def merge_inversions(nums):n = len(nums)if n <= 1:return 0, numsmid = n // 2cnt_l, left = merge_inversions(nums[:mid])cnt_r, right = merge_inversions(nums[mid:])i, j = 0, 0res = []cnt = 0while i < mid and j < n - mid:if left[i] > right[j]:res.append(right[j])j += 1cnt += mid - i # 注意这里，是left从i到结尾都是算逆序else:res.append(left[i])i += 1res += left[i:]res += right[j:]# print(cnt, cnt_l, cnt_r)return cnt + cnt_l + cnt_r, res
n = int(input())
nums = list(map(int, input().split()))
cnt, _ = merge_inversions(nums)
print(cnt)
完
感谢你看到这里！一起加油吧！