国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

python 堆排序

genedna / 2181人閱讀

摘要：堆排序堆排序是指利用堆這種數據結構所設計的一種排序算法。堆排序可以說是一種利用堆的概念來排序的選擇排序。代碼實現構建堆由下往上構建所以用每次踢掉求出的最大值

堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點（但是不保證所有左子樹比右子樹小反之亦然）。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；

小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間復雜度為 Ο(nlogn)。

算法步驟 
創建一個堆 H[0……n-1]；（**對非葉子節點的子節點進行調節，構建堆**）

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

重復步驟 2，直到堆的尺寸為 1。
Python 代碼實現 
def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/44979.html

相關文章

  • 八大排序算法的Python實現

    摘要：是穩定的排序方法。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。算法實現選擇排序堆排序描述堆排序是指利用堆積樹堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。 1、插入排序 描述 插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定...

    princekin 評論0 收藏0

  • Python 的 heapq 模塊源碼分析

    摘要：原文鏈接起步模塊實現了適用于列表的最小堆排序算法。本文內容將分為三個部分，第一個部分簡單介紹模塊的使用第二部分回顧堆排序算法第三部分分析中的實現。總結堆排序結合圖來理解還是比較好理解的。 原文鏈接：https://www.hongweipeng.com/i... 起步 heapq 模塊實現了適用于Python列表的最小堆排序算法。 showImg(https://segmentfaul...

    CoderBear 評論0 收藏0

  • 排序算法

    摘要：排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了，重復，，的操作，直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現：Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    kevin 評論0 收藏0

  • 排序算法

    摘要：排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了，重復，，的操作，直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現：Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    binaryTree 評論0 收藏0

  • python之排序操作及heapq模塊

    摘要：內置的模塊接下來我們一一介紹。小伙伴們有沒有想我為何介紹這個模塊，并且和排序放在一起呢，其實在很多時候我們需要找序列中的前幾個最大值或者最小值，使用此模塊中的方法是最好不過的了。 說到排序，很多人可能第一想到的就是sorted,但是你可能不知道python中其實還有還就中方法喲，并且好多種場景下效率都會比sorted高。那么接下來我就依次來介紹我所知道的排序操作。sorted(iter...

    dongfangyiyu 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<