介绍一种新的排序算法，归并排序。
总的来说，前面介绍了两种排序算法，冒泡排序（选择排序）和插入排序（希尔排序）。冒泡排序是依次两两对比，选取较大的进行比较，时间复杂度均为O(n2)；插入排序是依次选取一个元素，将其插入到排好序的有序表中（类似于有序链表的插入操作）。插入排序的是按复杂度也是O(n2）。希尔排序在选择最优的间隔序列后，时间复杂度为O(n^(3/2))
归并排序是一种基于分治策略的排序算法。将总的待排序列分成若干个小的子序列，然后分别对其进行排序。排完序后对子序列逐步进行归并。

思路：归并排序采用递归的形式，每次将当前序列分为两部分，递归，直到每个子序列只有一个元素，这样每个子序列其实就是有序的了，然后递归返回，接下来就是归并的过程了，想一想如何将留两个有序的序列合并为一个有序的序列？（可以看出来，归并排序的主要过程其实就是归并的过程）

没错，就是各自从前往后遍历比较，（默认是从小到大排列，升序）比如取出A序列的第一个元素，取出B序列的第一个元素，如果A中第一个元素小于B中的第一个元素。那么将A中的第一个元素加入到新的有序序列中，取出A中的第二个元素，与B中的第一个元素进行比较，哪个小就把他加入新的有序序列，并取出该序列的下一个元素，以此类推。直到有一个序列遍历完，那么 剩下的那个部分序列就直接原封不动加入到新的序列中就好了（因为本来就是有序的）。

这是教程给的代码1

# 归并排序1
def merge_sort(alist):

    if len(alist) > 1:
        mid = len(alist) // 2
        left_half = alist[:mid]
        right_half = alist[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = 0
        j = 0
        k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                alist[k] = left_half[i]
                i = i + 1
            else:
                alist[k] = right_half[j]
                j = j + 1

            k = k + 1

        while i < len(left_half):
            alist[k] = left_half[i]
            i = i + 1
            k = k + 1

        while j < len(right_half):
            alist[k] = right_half[j]
            j = j + 1
            k = k + 1

alist = [2,7,5,84,10,1,3,9,8,6]
# alist = [2,1,1,1,1,1,1,1,1]
merge_sort(alist)
print(alist)123456789101112131415161718192021222324252627282930313233343536373839

这是教程给的代码2，比较Python化，充分利用了Python的语法以及便捷性

# 归并排序2
def merge_sort(alist):

    if len(alist) <= 1:
        return alist

    middle = len(alist) // 2
    left = merge_sort(alist[:middle])
    right = merge_sort(alist[middle:])

    merged = []

    while left and right:

        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(right if right else left)

    return merged


alist = [2,7,5,84,10,1,3,9,8,6]
# alist = [2,1,1,1,1,1,1,1,1]
print(merge_sort(alist))123456789101112131415161718192021222324252627

这是我自己写的（其实是看了教程给的代码后才写出来的┭┮﹏┭┮）。因为本来之前是用C学的算法课，所以对Python还是一时转不过弯来。

# 归并排序

def merge_sort(alist):

	# 这是递归终止条件，还是用<=比较好，否则如果传过来是一个空列表就会报错
    if len(alist) <= 1:
        return alist
    else:

        # 分割序列
        left = alist[:len(alist) // 2]
        right = alist[len(alist) // 2:]

        # 分别排序
        left_list = merge_sort(left)
        right_list = merge_sort(right)

        # 归并两个子序列
        i = 0
        j = 0
        k = 0

        new_list = []
        while i < len(left_list) and j < len(right_list):
            if left_list[i] <= right_list[j]:
                new_list.append(left_list[i])
                i += 1
            else:
                new_list.append(right_list[j])
                j += 1

        while i < len(left_list):
            new_list.append(left_list[i])
            i += 1

        while j < len(right_list):
            new_list.append(right_list[j])
            j += 1

        return new_list



alist = [2,7,5,84,10,1,3,9,8,6]
# alist = [2,1,1,1,1,1,1,1,1]
print(merge_sort(alist))12345678910111213141516171819202122232425262728293031323334353637383940414243444546

时间复杂度为O(nlogn)。可以看成是两个部分，一个是分裂，一个是归并。分裂的时间复杂度和二分查找的类似，就是直到每个序列剩余一个时就终止，即n/(2^i)=1，i为logn。归并的过程其实在数量级上来说就是两两对比了，O(n)的时间复杂度。因为整个过程是分裂后再归并，即每次分裂都对应着一次归并。所以时间复杂度为O(nlogn)。

作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108374774

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。