# Python排序算法_归并排序和堆排序的python实现

XAMPP案例 52浏览

1. 归并排序

``def MergeSort(array):``    if len(array)< 2:``        return array``    else:   #递归地二分为左区和右区``        mid=int(len(array)/2)``        left=MergeSort(array[:mid])``        right=MergeSort(array[mid:])``    #左区和右区合并``    i,j=0,0``    new=[]``    while i<len(left) and j<len(right):``        if left[i]<right[j]:``            new.append(left[i])``            i=i+1``        else:``            new.append(right[j])``            j=j+1``    new=new+left[i:]+right[j:]``    return new``

2. 堆排序

python实现大根堆的升序排序算法:

``def max_root(array,len,root): # 调整堆元素并保证以root为根的堆是大根堆``    l=2*root+1``    r=2*root+2``    largest=root``    if l<len and array[largest]<array[l]:``        largest=l``    if r<len and array[largest]<array[r]:``        largest=r``    if largest!=root:``        array[root],array[largest]=array[largest],array[root]``        max_root(array,len,largest)  #对调整节点的子树进行堆调整``def HeapSort(array):``    n=len(array)``    for i in range((n-2)//2,-1,-1):   # 构造堆,自底向上``        max_root(array,n,i)``    for i in range(n-1,-1,-1):   # 将根节点元素array[0]取出与最后一位元素对调，对未取出节点继续进行堆调整``        array[i],array[0]=array[0],array[i]    ``        max_root(array,i,0)  #对末尾元素变为根节点后，进行堆调整``    return array``if __name__=='__main__':``    arr=[5,3,4,2,7]``    HeapSort(arr)``    print(arr)``
 排序算法 时间复杂度 稳定性 归并排序 nlogn 稳定 堆排序 nlogn 不稳定

1. 归并排序

``def MergeSort(array):``    if len(array)< 2:``        return array``    else:   #递归地二分为左区和右区``        mid=int(len(array)/2)``        left=MergeSort(array[:mid])``        right=MergeSort(array[mid:])``    #左区和右区合并``    i,j=0,0``    new=[]``    while i<len(left) and j<len(right):``        if left[i]<right[j]:``            new.append(left[i])``            i=i+1``        else:``            new.append(right[j])``            j=j+1``    new=new+left[i:]+right[j:]``    return new``

2. 堆排序

python实现大根堆的升序排序算法:

``def max_root(array,len,root): # 调整堆元素并保证以root为根的堆是大根堆``    l=2*root+1``    r=2*root+2``    largest=root``    if l<len and array[largest]<array[l]:``        largest=l``    if r<len and array[largest]<array[r]:``        largest=r``    if largest!=root:``        array[root],array[largest]=array[largest],array[root]``        max_root(array,len,largest)  #对调整节点的子树进行堆调整``def HeapSort(array):``    n=len(array)``    for i in range((n-2)//2,-1,-1):   # 构造堆,自底向上``        max_root(array,n,i)``    for i in range(n-1,-1,-1):   # 将根节点元素array[0]取出与最后一位元素对调，对未取出节点继续进行堆调整``        array[i],array[0]=array[0],array[i]    ``        max_root(array,i,0)  #对末尾元素变为根节点后，进行堆调整``    return array``if __name__=='__main__':``    arr=[5,3,4,2,7]``    HeapSort(arr)``    print(arr)``
 排序算法 时间复杂度 稳定性 归并排序 nlogn 稳定 堆排序 nlogn 不稳定