堆排序

堆排序属于选择排序的一种。

算法原理

堆排序是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序，具体来说，堆排序通过构建最大堆或者最小堆来实现排序。

1. 构建最大堆（建堆）：将待排序的列表视为完全二叉树，并根据列表中的元素构建最大堆。从最后一个非叶子节点开始，对每个节点进行堆化操作，将当前节点与其子节点进行比较并交换，以确保最大堆的性质。
2. 排序：经过第一步的构建最大堆，列表的第一个元素是最大堆的根节点，也是列表中的最大元素。将根节点与列表的最后一个元素交换，然后将最后一个元素从堆中移除。此时，列表中的最大元素已经就位。然后对剩余的元素进行堆化操作，得到新的最大堆。重复该过程，直到所有元素都被就位。

import random
import time
def heapify(nums,n,i):
    largest=i   #将当前节点标记为最大值
    left=2*i+1
    right=2*i+2
    #比较左子节点与当前节点的值
    if left<n and nums[largest]<nums[left]:
        largest = left
    if right<n and nums[largest]<nums[right]:
        largest=right
    #如果最大值不是当前节点，则交换它们，并继续堆化操作
    if largest!=i:
        nums[largest],nums[i] = nums[i],nums[largest]
        heapify(nums,n,largest)

def buildMaxHeap(nums):
    n=len(nums)
    #从最后一个非叶子节点开始进行堆化操作
    for i in range(n//2-1,-1,-1):
        heapify(nums,n,i)
def heapSort(nums):
    n=len(nums)
    #构建最大堆
    buildMaxHeap(nums)
    #逐个将最大值移动到列表末尾，然后重新堆化剩余的元素
    for i in range(n-1,0,-1):
        nums[i],nums[0]=nums[0],nums[i]
        heapify(nums,i,0)

    return nums
myList=[4,2,6,1]
startTime=time.time()
heapSort(myList)
endTime=time.time()
print(f"Sorted{myList} in {endTime-startTime}")

复杂度分析