Java堆排序是什么

這篇文章主要講解了“Java堆排序是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java堆排序是什么”吧！

  堆是指具有下列性質的完全二叉樹     完全二叉樹 i的雙親是[i/2]

         根節點一定最大或者最小 ！

         1 每個節點的值>=其左右節點的值   大頂堆

         2 每個節點的值<=其左右節點的值   小頂堆

        堆排序 Heap Sort  就是利用堆進行排序  如大頂堆。 將帶排序的數列構造程一個大頂堆 然后將跟節點與堆數組末尾元素互換，然后將剩下的n-1個序列重新構造成堆  往返進行。

堆排序（Heap Sort）只需要一個記錄元素大小的輔助空間（供交換用），每個待排序的記錄僅占有一個存儲空間。

堆的存儲

　　一般用數組來表示堆，若根結點存在序號0處， i結點的父結點下標就為(i-1)/2。i結點的左右子結點下標分別為2*i+1和2*i+2。

　　（注：如果根結點是從1開始，則左右孩子結點分別是2i和2i+1。）

　　如第0個結點左右子結點下標分別為1和2。

　　如最大化堆如下：

　　左圖為其存儲結構，右圖為其邏輯結構。

　　　1.如何由一個無序序列建成一個堆？

　　　2.如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？

        堆排序方法對記錄數較少的文件并不值得提倡，但對n較大的文件還是很有效的。因為其運行時間主要耗費在建初始堆和調整建新堆時進行的反復“篩選”上。

　　堆排序在最壞的情況下，其時間復雜度也為O(nlogn)。相對于快速排序來說，這是堆排序的最大優點。此外，堆排序僅需一個記錄大小的供交換用的輔助存儲空間。

堆排的時間復雜度為O(n log 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為父節點的子樹不是堆
        }
    }

}
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堆排序是什么”的內容了，經過本文的學習后，相信大家對Java堆排序是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！