最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

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

XAMPP案例 admin 52浏览 0评论

1. 归并排序

将元素从中间位置进行二分,左区和右区分别保证升序排列,各区的升序排列仍然继续二分,最后达到基准条件时,各区的元素个数少于2时返回该元素,最后依次合并各区完成排序。

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. 堆排序

堆是完全二叉树,任一非终端节点的数据值均不大于(或不小于)其左子节点和右子节点的值。大根堆:根结点的键值是所有堆结点键值中最大者;小根堆:根结点的键值是所有堆结点键值中最小者。

BA00000040

一维数组表示的大根堆

其中,父节点i的左子节点位置为(2*i+1);父节点i的右子节点位置为(2*i+2);子节点i的父节点位置为(i-1)//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. 归并排序

将元素从中间位置进行二分,左区和右区分别保证升序排列,各区的升序排列仍然继续二分,最后达到基准条件时,各区的元素个数少于2时返回该元素,最后依次合并各区完成排序。

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. 堆排序

堆是完全二叉树,任一非终端节点的数据值均不大于(或不小于)其左子节点和右子节点的值。大根堆:根结点的键值是所有堆结点键值中最大者;小根堆:根结点的键值是所有堆结点键值中最小者。

一维数组表示的大根堆

其中,父节点i的左子节点位置为(2*i+1);父节点i的右子节点位置为(2*i+2);子节点i的父节点位置为(i-1)//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 不稳定

转载请注明:XAMPP中文组官网 » Python排序算法_归并排序和堆排序的python实现