摘要:堆排序堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。代碼實(shí)現(xiàn)構(gòu)建堆由下往上構(gòu)建所以用每次踢掉求出的最大值
堆排序
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu),并同時(shí)滿足堆積的性質(zhì):即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)(但是不保證所有左子樹(shù)比右子樹(shù)小反之亦然)。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。分為兩種方法:
大頂堆:每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值,在堆排序算法中用于升序排列;
小頂堆:每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值,在堆排序算法中用于降序排列;
堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。
算法步驟創(chuàng)建一個(gè)堆 H[0……n-1];(**對(duì)非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行調(diào)節(jié),構(gòu)建堆**) 把堆首(最大值)和堆尾互換; 把堆的尺寸縮小 1,并調(diào)用 shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置; 重復(fù)步驟 2,直到堆的尺寸為 1。Python 代碼實(shí)現(xiàn)
def buildMaxHeap(arr): import math for i in range(math.floor(len(arr)/2),-1,-1):#構(gòu)建堆由下往上構(gòu)建所以用-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
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/44979.html
摘要:是穩(wěn)定的排序方法。也稱縮小增量排序,是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。算法實(shí)現(xiàn)選擇排序堆排序描述堆排序是指利用堆積樹(shù)堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的一種。 1、插入排序 描述 插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù),算法適用于少量數(shù)據(jù)的排序,時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定...
摘要:原文鏈接起步模塊實(shí)現(xiàn)了適用于列表的最小堆排序算法。本文內(nèi)容將分為三個(gè)部分,第一個(gè)部分簡(jiǎn)單介紹模塊的使用第二部分回顧堆排序算法第三部分分析中的實(shí)現(xiàn)。總結(jié)堆排序結(jié)合圖來(lái)理解還是比較好理解的。 原文鏈接:https://www.hongweipeng.com/i... 起步 heapq 模塊實(shí)現(xiàn)了適用于Python列表的最小堆排序算法。 showImg(https://segmentfaul...
摘要:排序代碼實(shí)現(xiàn)和一概念排序算法的穩(wěn)定性穩(wěn)定性穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。交換的結(jié)果導(dǎo)致結(jié)點(diǎn)的值變化了,重復(fù),,的操作,直到?jīng)]有孩子時(shí)跳出代碼實(shí)現(xiàn)構(gòu)建初始堆堆排序算法思想大頂堆舉例將待排序的序列構(gòu)造成一個(gè)大頂堆。 排序 代碼實(shí)現(xiàn):Java 和 Python 一、概念 1.1 排序算法的穩(wěn)定性 穩(wěn)定性:穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序...
摘要:排序代碼實(shí)現(xiàn)和一概念排序算法的穩(wěn)定性穩(wěn)定性穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。交換的結(jié)果導(dǎo)致結(jié)點(diǎn)的值變化了,重復(fù),,的操作,直到?jīng)]有孩子時(shí)跳出代碼實(shí)現(xiàn)構(gòu)建初始堆堆排序算法思想大頂堆舉例將待排序的序列構(gòu)造成一個(gè)大頂堆。 排序 代碼實(shí)現(xiàn):Java 和 Python 一、概念 1.1 排序算法的穩(wěn)定性 穩(wěn)定性:穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序...
摘要:內(nèi)置的模塊接下來(lái)我們一一介紹。小伙伴們有沒(méi)有想我為何介紹這個(gè)模塊,并且和排序放在一起呢,其實(shí)在很多時(shí)候我們需要找序列中的前幾個(gè)最大值或者最小值,使用此模塊中的方法是最好不過(guò)的了。 說(shuō)到排序,很多人可能第一想到的就是sorted,但是你可能不知道python中其實(shí)還有還就中方法喲,并且好多種場(chǎng)景下效率都會(huì)比sorted高。那么接下來(lái)我就依次來(lái)介紹我所知道的排序操作。sorted(iter...
閱讀 3319·2021-11-08 13:12
閱讀 2756·2021-10-15 09:41
閱讀 1451·2021-10-08 10:05
閱讀 3300·2021-10-08 10:04
閱讀 2102·2021-09-29 09:34
閱讀 2472·2019-08-30 15:55
閱讀 2979·2019-08-30 15:45
閱讀 2577·2019-08-29 14:17