二路归并排序Python实现

看了网上一些写法，总感觉有点复杂，所以我参考之前写的程序，用Python 改写了一个二路归并排序算法。

二路归并排序主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。

核心伪代码：

def MergeSort(array,p,q):
if p< q:
# 转成int 类型
mid =int((p+q)/2)

# 左边排序
MergeSort(array,p,mid)

#右边排序
MergeSort(array,mid+1,q)

# 进行merge，把已经排序的的数组，进行整体的合并
Merge(array,p,mid,q)

下面看代码

# coding=utf-8
'''
@author:chang
二路 归并排序 ，Python  实现
MergeSort(array,p,q)


 Merge(array,low,middle,high)  对这个函数进行，对array 进行merge ，就是 把array ，
 前半部分是已经排序，  后半部分已经排序
 把 array  组成一个新的array， Merge 就是把 array 左半部分，和右半部分分别 取出一个值比较，谁小 ，谁就放在arr[] 数组里面，
 最后如果 left_array 有剩余， 直接 copy 到 array[]数组里面；
 left_array 有剩余， 直接 copy 到 array[]数组里面。
'''

import  time
import  sys

def  Merge(array,low,middle,high):
    n1 = middle -low +1;
    n2 = high-middle
    left_array=[]
    right_array=[]

    # 可以理解相当于申请一块空间
    for t in range(0, int(n1)):
        left_array = ['0'] + left_array

    for t in range(0, int(n1)):
        right_array = ['0'] + right_array

    # 把array 左边的值，放到left_arr  数组里面
    for i in range(0,n1):
        left_array[i]=array[i+low]

    # 把 array 右边的值，放到 right_arr  数组里面
    for j in range(0,n2):
        right_array[j]=array[j+middle+1]

    i,j =0,0
    k = low
    while  i!=n1 and j !=n2:
        if left_array[i]<= right_array[j]:
            array[k]=left_array[i]
            k += 1
            i += 1
        else:
            array[k]=right_array[j]
            k += 1
            j += 1

           
    while i < n1:
        array[k]=left_array[i]
        k += 1
        i += 1

    while j< n2:
        array[k]=right_array[j]
        k += 1
        j += 1


def  MergeSort(array,p,q):
    if p< q:
        # 转成int  类型
        mid =int((p+q)/2)
        MergeSort(array,p,mid)
        MergeSort(array,mid+1,q)
        Merge(array,p,mid,q)


if __name__=="__main__":
    # mylist=[1,45,56,34,67,88,54,22]
    mylist = [1, 34, 6, 21, 98, 31, 7, 4, 56, 59, 27, 13, 36, 47, 67, 37, 25, 2]

    length = len(mylist)
    MergeSort(mylist, 0, length-1);

    print(mylist)

更新时间:2018-04-04 22:52:23

更新 : 对于merge 操作, 可以直接, 通过 [None]*n 来先生成好. 而不需要我之前的写法. 那个不是python 的风格. 这样写更像Python 风格的代码.

def Merge(array, low, middle, high):
    n1 = middle - low + 1
    n2 = high - middle
    left_array = [None]*n1
    right_array = [None]*n2

    # 把array 左边的值，放到left_arr  数组里面
    for i in range(0, n1):
        left_array[i] = array[i + low]

    # 把 array 右边的值，放到 right_arr  数组里面
    for j in range(0, n2):
        right_array[j] = array[j + middle + 1]

    i, j = 0, 0
    k = low
    while i != n1 and j != n2:
        if left_array[i] <= right_array[j]:
            array[k] = left_array[i]
            k += 1
            i += 1
        else:
            array[k] = right_array[j]
            k += 1
            j += 1

    while i < n1:
        array[k] = left_array[i]
        k += 1
        i += 1

    while j < n2:
        array[k] = right_array[j]
        k += 1
        j += 1

下面看结果：