归并排序

归并排序采用的是分治法的思想来进行排序的。

基本思想：分治法

分：先递归分解数组，将数组分解成最小的一个个元素

治：分解后的数组依次进行排序，最后合并数组。

最后得到了排好序的数组。

此处借鉴一张网上的图

时间复杂度：O(nlogn)

注意：归并排序是稳定的排序

代码：

def merge(left_arr, right_arr):
    """合并操作：将两个有序数组合并为一个有序数组"""

    left_index, right_index = 0, 0  # left_index, right_index 分别表示左边列表和右边列表的索引号
    result = []

    # 当左边列表或者右边列表走到头了，循环结束
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] < right_arr[right_index]:
            result.append(left_arr[left_index])
            left_index += 1
        else:
            result.append(right_arr[right_index])
            right_index += 1
    result += (left_arr[left_index:])   # 把多余一边的元素给加到 result 列表中
    result += (right_arr[right_index:])
    return result

# 归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    merge_arr = merge(left_arr, right_arr)
    return merge_arr

调用归并排序：

nums = [1,3,2,4,7,5,6,8,10,9]
print(merge_sort(nums))

输出结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

'''
将序列分成左右两份，然后对每一份再进行该操作，直至分为长度为2或者一为止
然后对最小序列进行排序，排序之后返回上一层，合并排序之后的两个子序列。
直至返回到合并成原序列大小位置，此时排序完成
'''
def divide(list):
    if len(list) > 2:
        return list[:len(list) // 2], list[len(list) // 2:]
    else:
        return list


def panduan(list_left, list_right):
    list_final = []
    while len(list_left) > 0 and len(list_right) > 0:
        if list_left[0] <= list_right[0]:
            list_final.append(list_left[0])
            list_left.pop(0)
        else:
            list_final.append(list_right[0])
            list_right.pop(0)
    if len(list_right) != 0:
        list_final.extend(list_right)
    if len(list_left) != 0:
        list_final.extend(list_left)
    return list_final


def mergeSort(list):
    list_divided = divide(list)
    list_origin = []
    for ele in list_divided:
        if len(ele) > 2:
            ele = mergeSort(ele)
        elif len(ele) != 1:
            ele = panduan(ele[:len(ele)//2], ele[len(ele)//2:])
        list_origin.extend(ele)
    return panduan(list_origin[:(len(list)//2)], list_origin[(len(list)//2):])


a = [12, 34, 15, 2, 45, 48, 231, 5, 13]
list_final = mergeSort(a)
print(list_final)

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治法:

• 分割：递归地把当前序列平均分割成两半。
• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

一.方法思想

归并排序(MergeSort)的基本思想是：将待排序文件看成为n个长度为1的有序子文件，把这些子文件两两归并，使得到「n/2」个长度为2的有序子文件；然后再把这「n/2」个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止，这种排序方法成为二路归并排序。例如，有初始关键字序列：72,18,53,36,48,31,36，其二路归并排序过程如下所示。

二.时间复杂度

归并排序时间复杂度为O(nlogn)，平均时间复杂度O(nlogn)最好和最坏时间复杂度(nlogn)。归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(logn)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O(n)

三.代码实现

要判断递归的终止条件

def merge(li,low,mid,high):
    i = low 
    j = mid + 1
    ltmp =[]
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    #当while执行完毕时，肯定有一部分没有数了
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp
        
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)
    #递归终止的条件是当low = high 时，此时只有一个元素，递归终止
    return li

我们创建一个列表并利用merge_sort函数实现归并排序。

import random
li = list(range(100))
random.shuffle(li)
print(merge_sort(li,0,len(li)-1))

输出结果：

 以上就是归并排序的全部内容了。