归并排序

• 概述
  • 以归并操作为基础的排序算法，底层算法设计为分治法。
  • 所谓分治法，就是讲问题分解为多个子问题递归求解，再将子问题答案合并。
• 算法实现
  • 将待排序序列分解为两个，四个，，，n个子部分。
  • 两两合并，并内部排序。

• 算法分析

  • 这个算法描述比较简单，然而实现起来略有难度，递归迭代法均可解。

  • 复杂度

    排序名称	最好情况	最坏情况	平均情况
    快速排序	O(nlog2n)	O(nlog2n)	O(nlog2n)

  • 稳定性
    • 算法稳定。
  • 优先选择
    • 从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
    • 从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
    • 从平均情况下的排序速度考虑，应该选择快速排序。

# -*- coding:UTF-8 -*-
def MergeSort(data=[1, 2, 3, 4, 5]):
    def merge(data, left, middle, right, temp):
        \'\'\'
        合并函数
        :param data: 待合并列表
        :param left:左指针
        :param middle:
        :param right:右指针
        :param temp:
        :return:None
        \'\'\'
        i = left
        j = middle + 1
        k = 0
        while i <= middle and j <= right:
            if data[i] <= data[j]:
                temp[k] = data[i]
                i += 1
            else:
                temp[k] = data[j]
                j += 1
            k += 1
        while i <= middle:
            temp[k] = data[i]
            i += 1
            k += 1
        while j <= right:
            temp[k] = data[j]
            j += 1
            k += 1
        k = 0
        while left <= right:
            data[left] = temp[k]
            left += 1
            k += 1

    def mergeSort(data, left, right, temp):
        print(data)
        if left < right:
            middle = (left + right) // 2
            mergeSort(data, left, middle, temp)
            mergeSort(data, middle+1, right, temp)
            merge(data, left, middle, right, temp)

    temp = [0]*len(data)
    mergeSort(data, 0, len(data)-1, temp)
    print(data)
    return data


if __name__ == \'__main__\':
    testData = [6, 5, 4, 3, 2, 7, 1]
    MergeSort(testData)

具体可以查看我的github。