python归并排序

python之归并排序
归并排序运用的是分治法，不断分割，将大问题转化为一个个小问题，递归简化求解，即分而治之。

第一种：

#归并排序代码
def guibing(a,b):
    c=[]
    h=j=0
    while j 
第二种：
 
# 归并排序
#这是合并的函数
# 将序列L[first...mid]与序列L[mid+1...last]进行合并
def guibingarray(array,first,mid,last,temp):
#对i,j,k分别进行赋值
    i,j,k = first,mid+1,0
#当左右两边都有数时进行比较，取较小的数
    while (i <= mid) and (j <= last):
        if array[i] <= array[j]:
            temp[k] = array[i]
            i = i+1
            k = k+1
        else:
            temp[k] = array[j]
            j = j+1
            k = k+1
#如果左边序列还有数
    while (i <= mid):
        temp[k] = array[i]
        i = i+1
        k = k+1
#如果右边序列还有数
    while (j <= last):
        temp[k] = array[j]
        j = j+1
        k = k+1
#将temp当中该段有序元素赋值给L待排序列使之部分有序
    for x in range(0,k):
        array[first+x] = temp[x]
# 这是分组的函数
def guibing_sort(v,first,last,temp):
    if first < last:
        mid = (int)((first + last) / 2)
        guibing_sort(array,first,mid,temp)   #使左边序列有序
        guibing_sort(array,mid+1,last,temp)  #使右边序列有序
        guibingarray(array,first,mid,last,temp)#将两个有序序列合并
    return L
    
def guibing_sort_array(array):    # 归并排序的函数
    temp = len(array)*[None]      #声明一个长度为len(L)的空列表
    return guibing_sort(array,0,len(array)-1,temp)   #调用归并排序
if __name__=='__main__':
    L = [10, 17, 50, 7, 30, 24, 27, 45]
    print(guibing_sort_array(L))
 
可以很容易理解递归深度应该为lgn，下面为图例演示：
 

 归并排序是作为一种稳定的排序，它也是一种十分高效的排序。每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。总的来说，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。