目录
什么是归并排序
归并排序(Merge Sort)是一种经典的排序算法,它采用分治策略来将一个大问题分解成小问题,然后将小问题的结果合并起来得到最终的解决方案。归并排序的核心思想是将待排序的数组不断地二分,直到每个子数组的长度为1,然后再将相邻的子数组合并成一个有序的数组(合并的连两个子数组各自应该是有序的),最终得到完全有序的数组。算法平均时间复杂度为O(nlogn)。
算法思想
归并排序的具体过程可以分为两个主要步骤:分解(Divide)和合并(Merge)。
-
分解(Divide):
首先,将待排序的数组递归地二分为两个子数组,直到每个子数组的长度为1。这里使用递归的方式将数组一分为二,直到无法再分解为止。
-
合并(Merge):
将相邻的两个子数组合并成一个有序的数组。这里使用一个辅助数组来存储合并后的结果。
从两个子数组的起始位置开始,依次比较两个子数组中的元素大小,将较小的元素放入辅助数组中,并将相应的指针向后移动。
当其中一个子数组的所有元素都放入辅助数组后,将另一个子数组中剩余的元素直接放入辅助数组中。
最后,将辅助数组中的元素复制回原始数组的相应位置,完成合并过程。
代码示例
def merge(li, low, mid, high):
i = low
j = mid + 1
merge_list = []
while i <= mid and j <= high:
if li[i] < li[j]:
merge_list.append(li[i])
i += 1
if li[i] > li[j]:
merge_list.append(li[j])
j += 1
while i <= mid:
merge_list.append(li[i])
i += 1
while j <= high:
merge_list.append(li[j])
j += 1
li[low:high+1] = merge_list
def merge_sort(li, low, high):
if low < high: # 递归实现
mid = (low+high) // 2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)
# print(li[low:high+1])
标签:归并,辅助,七一,合并,算法,数组,排序
From: https://www.cnblogs.com/chase-youth/p/17931552.html