排序算法（5）：归并排序

问题

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

归并排序

归并排序采用分治法，将序列分成若干子序列，每个子序列有序后再合并成有序的完整序列。

在数组排序中，如果只有一个数，那么它本身就是有序的。如果有两个数，只需要进行一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，如果有一个由大量数据组成的序列，可以考虑将其不断分解，直到只剩一个数时，本身已经有序，再将这些有序的数组合并在一起，从而完成排序。

图解

1. 将待排序元素分成大小大致相同的两个序列
2. 对两个序列分别进行归并排序
3. 将排好序的有序子序列进行合并，得到最终的有序序列
   

代码

# 合并, 将两个有序的子序列合并成一个序列
def merge(nums, low, mid, high):
    i, j = low, mid + 1
    k = 0
    temp = [0] * (high - low + 1)

    while i <= mid and j <= high:

        if nums[i] <= nums[j]:
            temp[k] = nums[i]
            i += 1
        else:
            temp[k] = nums[j]
            j += 1
        k += 1

    if i <= mid:
        temp[k:] = nums[i:mid+1]
    if j <= high:
        temp[k:] = nums[j:high+1]

    nums[low:high+1] = temp

    return nums
    

def merge_sort(nums, low = 0, high = len(nums)-1):
    if low < high:# low = high时分解到只剩一个数，不用合并直接返回
        mid = low + (high - low) // 2
        merge_sort(nums, low, mid)# 对左半部分进行归并排序
        merge_sort(nums, mid+1, high)# 对右半部分进行归并排序
        return merge(nums, low, mid, high)# 合并为有序子序列
    else:
        return nums

时间复杂度

归并算法的时间复杂度为 O(nlogn)

• 分解：这一步仅仅是计算出子序列的中间位置，需要常数时间 O(1)
• 解决子问题：递归求解两个规模为 n/2 的子问题，所需时间为 2T(n/2)
• 合并：合并算法可以在 O(n) 时间内完成

所以总运行时间为：

当 n>1 时，可以递推求解：

递推最终的规模为 1， 令 2^x = n，则 x = log n，那么

原文地址：https://blog.csdn.net/m0_45284589/article/details/144402178

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！