上一次尝试实现归并排序，直接将待排序数组拆分，这次遍历数组，遇到未按顺序的地方再进行分割。
#自编：改进后的归并排序
import math
node = [0]
def split_arr(arr):
global node
#使用extend而非append，避免多次调用append影响性能，下同
arr.append(-float('inf'))
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
node.append(i+1)
A = []
for j in range(len(node)-1):
A.append(arr[node[j]:node[j+1]])
return A
def merge(L, R):
res = []
n1 = len(L)
n2 = len(R)
L.append(float('inf'))
R.append(float('inf'))
i, j = 0, 0
for k in range(n1 + n2):
if L[i] <= R[j]:
res.append(L[i])
i += 1
else:
res.append(R[j])
j += 1
return res
arr_before = [3, 41, 52, 26, 38, 57, 9, 49]
A = split_arr(arr_before)
while len(A) > 1:
a = merge(A[-2], A[-1]) # 合并最后一个和倒数第二个元素
A = A[:-2] + [a] # 直接用合并后的新元素替换掉最后两个元素
print('after sort:', A[0])#由于A处理到最后，是一个只有一个元素的数组，所以直接输出A[0]即可
最坏的情况，时间复杂度为O(n log n)，空间复杂度为O(n)
快速排序
#快速排序
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # 选择中间元素作为基准
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# 示例
arr = [3, 41, 52, 26, 38, 57, 9, 49]
sorted_arr = quicksort(arr)
print(sorted_arr)
快速排序是一种高效的排序算法，由英国计算机科学家 Tony Hoare 在 1960 年提出。它的基本思想是使用分治法（Divide and Conquer）来解决问题：
选择基准（Pivot Selection）：
首先，选择一个基准元素。在这个例子中，基准是数组的中间元素（arr[len(arr) // 2]）。其他方法包括随机选择或三数取中法。 分区（Partitioning）：
将数组分为三个部分： left 子数组：包含所有小于基准的元素。 middle 子数组：包含所有等于基准的元素。 right 子数组：包含所有大于基准的元素。 递归排序：
对 left 和 right 子数组分别进行快速排序，这一步是递归的。由于这两个子数组都比原数组小，所以问题规模逐渐减小。 最终，将排序后的 left 子数组、middle 子数组（无需排序，因为元素已经等于基准）和排序后的 right 子数组连接起来，就得到了排序后的数组。 终止条件：
当数组长度小于或等于 1 时，我们知道数组已经是有序的，因此不需要再进行排序。这就是递归的基本停止条件。 这个例子中的快速排序实现是“非原地”的，因为它创建了新的子数组 left, middle, 和 right。原地快速排序可以减少内存使用，但实现更复杂。此外，快速排序在最坏情况下的时间复杂度是 O(n²)，当输入数组已经完全有序时。然而，平均时间复杂度是 O(n log n)，在实际应用中表现出良好的性能。