堆排序是指利用堆積樹這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。可以利用數(shù)組的特點快速定位指定索引的元素。堆是一個優(yōu)先級隊列，對于大頂堆而言，堆頂元素的權值最大。將待排序的數(shù)組建堆，然后不斷地刪除堆頂元素，就實現(xiàn)了排序。

堆排序基本思想

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列。

堆是具有下列性質的完全二叉樹：每個節(jié)點的值都大于或等于其左右孩子節(jié)點的值，稱為大根堆；每個節(jié)點的值都小于或等于其左右孩子節(jié)點的值，稱為小根堆。堆排序的最壞時間復雜度為O(n*log2n)，平均時間復雜度為O(n*log2n)。

堆排序算法復雜度

對N個元素建堆的時間復雜度為O(N)，刪除堆頂元素的時間復雜度為O(logN)，盡管隨著元素的不斷刪除，堆的調度越來越小，但是總的而言，刪除堆所有元素的時間復雜度為O(NlogN)。故堆排序的時間復雜度為O(NlogN)，空間復雜度為O(1)。

對于堆排序而言，數(shù)據(jù)的初始順序對它的復雜度沒有影響。不管數(shù)組初始時就是有序的還是逆序的，它都會先建堆，變成了堆序的性質。從這點上分析，堆排序是一個非常穩(wěn)定的算法，最壞和平均情況下的時間復雜度都為O(NlogN)。

堆排序的步驟

大根堆有一個很好的性質，根節(jié)點的數(shù)值總是大于其他所有節(jié)點的數(shù)值，利用大根堆的這個性質，可以實現(xiàn)排序的工作。步驟如下：

1、構建大根堆。首先我們的原始數(shù)組一般情況下是不滿足堆的條件，既然我們要可用大根段的性質進行排序，第一步當然是對原始數(shù)組進行處理，構建大根堆。

2、根節(jié)點數(shù)據(jù)處理以及大根堆重構。構建大根堆元素之后，根節(jié)點的元素是最大值。然后將該數(shù)值取出，對剩下的元素進行重構大根堆，這時根節(jié)點是剩下元素的最大值，取出。只要不斷重復上述的操作，不斷取出未排序元素的最大值，直到未排序的元素只剩一個，就完成了排序工作。

堆排序算法分析

堆排序的運行時間主要是消耗在初始構建堆和在重建堆時的反復篩選上。在構建堆的過程中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對于每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間復雜度為O(n)。

在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間(完全二叉樹的某個結點到根結點的距離為log2i＋1)，并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)。

總體來說，堆排序的時間復雜度為O(nlogn)。由于堆排序對原始記錄的排序狀態(tài)并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)。這在性能上顯然要遠遠好過于冒泡、簡單選擇、直接插入的O(n2)的時間復雜度。

再簡單總結下堆排序的基本思路：

A、將無需序列構建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;

B、將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;

C、重新調整結構，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調整和交換步驟，直到整個序列有序。

最后

堆排序是一種選擇排序，整體主要由構建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成。其中構建初始堆經(jīng)推導復雜度為O(n)，在交換并重建堆的過程中，元素需交換n-1次，而重建堆的過程中，根據(jù)完全二叉樹的性質，[log2(n-1),log2(n-2)...1]逐步遞減，近似為nlogn。所以堆排序時間復雜度一般認為就是O(nlogn)級。

總結

以上是生活随笔為你收集整理的堆排序时间复杂度_堆排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。