归并排序
1.关键点
分治思想，递归实现。
关键点是划分、递归的结构、merge的编写
具体参考代码实现对应
2.时空复杂度分析
这种类似二叉树的结构，时间复杂度一般是O(nlogn)。
具体的推导，写出递归公式
T(1) = C； n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2T(n/2) + n； n>1 # 这里的n是，merge中遍历两个数组的时间复杂度
T(n) = 2T(n/2) + n
= 2*(2T(n/4) + n/2) + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
= 8*(2T(n/16) + n/8) + 3n = 16T(n/16) + 4n
…
= 2^k * T(n/2^k) + k * n
取n/2^k=1，算出k=…,带入上面T(n)的最后一行即可
空间复杂度：merge中的临时数组使用O(n)
3.稳定排序算法
merge中的写法是不会改变相同大小元素的顺序的。过程中不改变，结局排好序的自然也不会改变
arr[i] <= arr[j]:
tmp_arr.append(arr[i])
i += 1
4.代码实现
class MergeSort:
def merge_sort(self, arr):
self.merge_sort_c(arr, 0, len(arr) - 1)
# merge_sort_complement
def merge_sort_c(self, arr, start_index, end_index):
# 采用分治的思想，使用递归的方式实现。指定mid_index = start_index + (end_start- start_index)
# 划分为两部分一直到无可划分（列表只有一个元素）
if start_index >= end_index:
return
mid_index = start_index + (end_index - start_index) // 2
# 展开联想:下面这个代码结构与后序遍历是相似的。
# 最后的merge是完成两个排好序的数组的合并。其实证明最后排序正确的过程可以参考数学归纳法。
self.merge_sort_c(arr, start_index, mid_index)
self.merge_sort_c(arr, mid_index + 1, end_index)
self.merge(arr, start_index, mid_index, end_index)
def merge(self, arr : list[int], start_index, mid_index, end_index):
tmp_arr = []
i = start_index
j = mid_index + 1
while i <= mid_index or j <= end_index:
# 指针移动到最后的两个边界情况
# 这里使用if elif 来写，因为除了两个边界，其余都是正常情况
if i > mid_index:
tmp_arr.append(arr[j])
j += 1
elif j > end_index:
tmp_arr.append(arr[i])
i += 1
elif arr[i] <= arr[j]:
tmp_arr.append(arr[i])
i += 1
else:
tmp_arr.append(arr[j])
j += 1
for i in range(start_index, end_index + 1):
arr[i] = tmp_arr[i - start_index]
if __name__ == '__main__':
arr = [9, 4, 4, 5, 6, 7, 3, 234, 6, 1]
test = MergeSort()
test.merge_sort(arr)
print(arr)
