Java堆排序是什么
這篇文章主要講解了“Java堆排序是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java堆排序是什么”吧！
樅陽網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、APP開發(fā)、成都響應式網(wǎng)站建設公司等網(wǎng)站項目制作，到程序開發(fā)，運營維護。成都創(chuàng)新互聯(lián)于2013年創(chuàng)立到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設就選成都創(chuàng)新互聯(lián)。
堆是指具有下列性質的完全二叉樹 完全二叉樹 i的雙親是[i/2]
根節(jié)點一定最大或者最小 ！
1 每個節(jié)點的值>=其左右節(jié)點的值 大頂堆
2 每個節(jié)點的值<=其左右節(jié)點的值 小頂堆
堆排序 Heap Sort 就是利用堆進行排序 如大頂堆。 將帶排序的數(shù)列構造程一個大頂堆 然后將跟節(jié)點與堆數(shù)組末尾元素互換，然后將剩下的n-1個序列重新構造成堆 往返進行。
堆排序（Heap Sort）只需要一個記錄元素大小的輔助空間（供交換用），每個待排序的記錄僅占有一個存儲空間。
堆的存儲
一般用數(shù)組來表示堆，若根結點存在序號0處， i結點的父結點下標就為(i-1)/2。i結點的左右子結點下標分別為2*i+1和2*i+2。
（注：如果根結點是從1開始，則左右孩子結點分別是2i和2i+1。）
如第0個結點左右子結點下標分別為1和2。
如最大化堆如下：
左圖為其存儲結構，右圖為其邏輯結構。
1.如何由一個無序序列建成一個堆？
2.如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？
堆排序方法對記錄數(shù)較少的文件并不值得提倡，但對n較大的文件還是很有效的。因為其運行時間主要耗費在建初始堆和調整建新堆時進行的反復“篩選”上。
堆排序在最壞的情況下，其時間復雜度也為O(nlogn)。相對于快速排序來說，這是堆排序的最大優(yōu)點。此外，堆排序僅需一個記錄大小的供交換用的輔助存儲空間。
堆排的時間復雜度為O(n log n). 不穩(wěn)定
#include <iostream>
#include <cstring>
using namespace std;
void HeapAdjust1(int a[], int pos, int n)//這個不太好理解
{
int temp = a[pos];
int child = 2*pos+1;
while(child<n)
{
if(child+1<n && a[child]<a[child+1])
{
child++;
}
if(a[pos]<a[child])
{
a[pos] = a[child];
pos = child;
child = 2*child+1;
}
else
{
break;
}
}
a[pos] = temp;
}void HeapAdjust(int a[], int pos, int n)
{
int max = pos;
int Left = 2*pos+1;
int Right = 2*pos+2;
if(pos<=(n-1)/2)
{
if(Left<n && a[max]<a[Left])
{
max = Left;
}
if(Right<n && a[max]<a[Right])
{
max = Right;
}
if(pos != max)
{
int temp =a[pos];
a[pos] = a[max];
a[max] = temp;
HeapAdjust(a, max,n);//避免調整之后以max為父節(jié)點的子樹不是堆
}
}}
void BuildHeap(int a[], int n)
{
for(int pos=(n-1)/2;pos>=0; --pos)
{
HeapAdjust(a,pos,n);
}
}
void HeapSort(int a[], int n)
{
BuildHeap(a, n);
for(int len = n-1;len>0; --len)
{
int temp = a[len];
a[len] = a[0];
a[0] = temp;
HeapAdjust(a, 0, len);
}
}
int main()
{
int a[9] = {9,1,5,8,3,7,4,6,2};
//ShellSort(a, 9);
HeapSort(a, 9);
for(int i=0;i<9;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}感謝各位的閱讀，以上就是“Java堆排序是什么”的內容了，經(jīng)過本文的學習后，相信大家對Java堆排序是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關知識點的文章，歡迎關注！
網(wǎng)站欄目：Java堆排序是什么
分享路徑：http://www.chinadenli.net/article14/jsiede.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、做網(wǎng)站、用戶體驗、微信小程序、網(wǎng)站導航、App開發(fā)
聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)
