堆排序是什么排序

發(fā)布時間：2020-07-31 10:16:42 來源：億速云閱讀：191 作者：Leah 欄目：互聯(lián)網(wǎng)科技

這期內(nèi)容當中小編將會給大家?guī)碛嘘P(guān)堆排序是什么排序，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

堆排序是一種將無序的序列生成一個最大堆，將堆頂元素與最后一個元素對換位置，并將剩下元素生成最大堆，依次進行元素交換并生成最大堆的排序。

堆排序

將無序的序列生成一個最大堆，將堆頂元素與最后一個元素對換位置，將剩下元素生成最大堆，依次進行元素交換并生成最大堆

時間復(fù)雜度：O(NlogN) 空間復(fù)雜度：O(1)

簡介：

堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

堆的操作

在堆的數(shù)據(jù)結(jié)構(gòu)中，堆中的最大值總是位于根節(jié)點（在優(yōu)先隊列中使用堆的話堆中的最小值位于根節(jié)點）。

堆中定義以下幾種操作：

最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點

創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序

堆排序（HeapSort）：移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調(diào)整的遞歸運算

上述就是小編為大家分享的堆排序是什么排序了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

猜你喜歡