一、堆排序

1、什么是堆排序

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

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

2、堆排序思想

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

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

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

3、代碼實(shí)現(xiàn)

import java.util.Arrays;
public class Sort {
     //將任意數(shù)組進(jìn)行原地堆排序
    public static void heapSort(int[] arr) {
        //把數(shù)組調(diào)整為最大堆，從最后一個(gè)非葉子節(jié)點(diǎn)開始下沉
        for (int i = (arr.length-1-1)/2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        //將堆頂元素和最后一個(gè)元素交換
        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));
    }
}

運(yùn)行截圖：

二、時(shí)間復(fù)雜度分析

1、初始化建堆

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

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

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

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

2、排序重建堆

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

所以時(shí)間復(fù)雜度為O(nlogn)

3、總結(jié)

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

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

最新評(píng)論