什么是堆排序呢，其時(shí)間復(fù)雜度是怎么計(jì)算的呢？堆排序是利用堆數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序算法。Heap是一種幾乎完全的二叉樹(shù)結(jié)構(gòu)，它滿足Heap的性質(zhì)：子節(jié)點(diǎn)的鍵值或索引總是小于（或大于）父節(jié)點(diǎn)。堆排序的平均

什么是堆排序呢，其時(shí)間復(fù)雜度是怎么計(jì)算的呢？

堆排序是利用堆數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序算法。Heap是一種幾乎完全的二叉樹(shù)結(jié)構(gòu)，它滿足Heap的性質(zhì)：子節(jié)點(diǎn)的鍵值或索引總是小于（或大于）父節(jié)點(diǎn)。

堆排序的平均時(shí)間復(fù)雜度為O（nlogn），空間復(fù)雜度為θ（1）。

堆排序中建堆過(guò)程時(shí)間復(fù)雜度O怎么來(lái)的？

冒泡排序，堆排序，快速排序，插入排序，歸并排序的的穩(wěn)定性及時(shí)間空間復(fù)雜度？

氣泡排序、插入排序、合并排序和基數(shù)排序都是穩(wěn)定排序。快速排序、選擇排序、堆排序和希爾排序都是不穩(wěn)定排序。冒泡排序、插入排序和選擇排序的時(shí)間復(fù)雜度為O（n^2），合并排序、堆排序和快速排序的時(shí)間復(fù)雜度為O（n*log（n）），冒泡排序、插入排序和選擇排序的空間復(fù)雜度為O（1），合并排序?yàn)镺（n）。

堆排序的空間復(fù)雜度為什么是O(1)的？

堆排序可以通過(guò)簡(jiǎn)單的交換將數(shù)據(jù)安排到適當(dāng)?shù)亩阎?，無(wú)需輔助空間。堆和原始數(shù)據(jù)是集成的。創(chuàng)建：heap | unprocessed data sort:heap | sorted data堆的大小和未處理/排序的數(shù)據(jù)加起來(lái)等于原始數(shù)據(jù)的大小。