当前位置:天才代写 > tutorial > Python教程 > python 算法之堆排序-python基础

python 算法之堆排序-python基础

2021-02-23 15:17 星期二 所属: Python教程 浏览:13

堆排序

堆排序(Heapsort)就是指运用堆这类算法设计所设计方案的一种快速排序算法。沉积是一个类似完全二叉树的构造,并另外考虑沉积的特性:即子节点的键值或数据库索引一直低于(或是超过)它的父节点。堆排序能够说成一种运用堆的定义来排列的选择排序。分成二种方式:

  1. 大顶堆:每一个连接点的值都大于或等于他的儿子连接点的值,在堆排序算法中用以升序排序;
  2. 小顶堆:每一个连接点的值都小于或等于他的儿子连接点的值,在堆排序算法中用以降序排序;

堆排序的均值算法复杂度为 Ο(nlogn)。

优化算法流程

  1. 建立一个堆 H[0……n-1];
  2. 把堆首(最高值)和堆尾交换;
  3. 把堆的规格变小 1,并启用 shift_down(0),目地是把新的二维数组顶部数据信息调节到相对部位;
  4. 反复流程 2,直至堆的规格为 1。

Python 编码完成

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i 1
    right = 2*i 2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr
 

    关键字:

天才代写-代写联系方式