一、堆排序

1、什么是堆排序

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

（2）堆是具有以下性質(zhì)的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

2、堆排序思想

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

（2）將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端

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

3、代碼實現(xiàn)

import java.util.Arrays;
public class Sort {
     //將任意數(shù)組進行原地堆排序
    public static void heapSort(int[] arr) {
        //把數(shù)組調(diào)整為最大堆，從最后一個非葉子節(jié)點開始下沉
        for (int i = (arr.length-1-1)/2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        //將堆頂元素和最后一個元素交換
        for (int i = arr.length-1; i > 0 ; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
   //下沉操作
    private static void siftDown(int[] arr, int i, int n) {
        while ((2 * i)+1 < n){
            int j = (2 * i) + 1;
            if(j+1<n && arr[j+1]>arr[j]){
               j = j+1;
            }
            if(arr[i] >= arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i = j;
            }
        }
    }
     public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+ Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }
}

運行截圖：

二、時間復雜度分析

1、初始化建堆

初始化建堆只需要對二叉樹的非葉子節(jié)點由下至上，由右至左選取非葉子節(jié)點來調(diào)用adjusthead()函數(shù)。那么倒數(shù)第二層的最右邊的非葉子節(jié)點就是最后一個非葉子結點。

　假設高度為k，則從倒數(shù)第二層右邊的節(jié)點開始，這一層的節(jié)點都要執(zhí)行子節(jié)點比較然后交換；倒數(shù)第三層呢，則會選擇其子節(jié)點進行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。高層也是這樣逐漸遞歸。

　那么總的時間計算為：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第幾層，2^( i - 1) 表示該層上有多少個元素，( k - i) 表示子樹上要下調(diào)比較的次數(shù)。

S = n - log(n) -1，所以時間復雜度為：O(n)

2、排序重建堆

每次重建意味著有一個節(jié)點出堆，所以需要將堆的容量減一。adjustheap()函數(shù)的時間復雜度k=log(n)，k為堆的層數(shù)。所以在每次重建時，隨著堆的容量的減小，層數(shù)會下降，函數(shù)時間復雜度會變化。重建堆一共需要n-1次循環(huán)，每次循環(huán)的比較次數(shù)為log(i)，則相加為：log2+log3+…+log(n-1)+log(n)≈log(n!)。

所以時間復雜度為O(nlogn)

3、總結

初始化建堆的時間復雜度為O(n)，排序重建堆的時間復雜度為nlog(n)，所以總的時間復雜度為O(nlogn)，空間復雜度為O（1）。

到此這篇關于Java詳細講解堆排序與時間復雜度的概念的文章就介紹到這了,更多相關Java堆排序與時間復雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論