写个归并排序吧~

def merge_sort(arr): if not arr or len(arr) == 1: return arr mid = (len(arr) - 1) // 2 return merge(merge_sort(arr[: mid + 1]), merge_sort(arr[mid + 1 :])) # 注意一定是 mid + 1, 而不是 mid, # 因为要保证两个子序列都严格小于原来的序列, 而 0 <= mid < len(arr) - 1 是确定的 def merge(p, q): res = [] i, j = 0, 0 while i < len(p) and j < len(q): # 双指针同向选择性移动, 注意终止条件 if p[i] <= q[j]: res.append(p[i]) i += 1 else: res.append(q[j]) j += 1 return res + p[i:] + q[j:] def quick_sort(arr): if not arr or len(arr) == 1: return arr k, new_arr = partition(arr) return quick_sort(new_arr[:k]) + [new_arr[k]] + quick_sort(new_arr[k + 1 :]) # 保证子序列一定严格小于原序列 def partition(arr): tmp = arr[-1] i, j = 0, 0 while j < len(arr): if arr[j] <= tmp: arr[j], arr[i] = arr[i], arr[j] # 交换 i += 1 j += 1 return i - 1, arr # 保证分界点 i - 1 上的值一定是 tmp # 测试通过 arr = [2, 1, 3, 4, 5, 10, 3, 2, 9] for i in range(len(arr) + 1): sorted_arr = merge_sort(arr[:i]) print(sorted_arr)

分治思维，双指针思维，一般要使用新的存储来返回值