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

關(guān)于具體實(shí)現(xiàn)過程請點(diǎn) https://blog.csdn.net/weixin_44324174/article/details/104183349
本片文章只講堆排序時間復(fù)雜度的計算過程。

package com.westmo1.demo2; import java.util.Arrays; import java.util.Scanner; public class MyDemo3 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("輸入數(shù)據(jù)");int[] ints = new int[7];for (int i = 0; i < ints.length; i++) {int i1 = scanner.nextInt();ints[i]=i1;}int length=ints.length-1;int root=ints.length/2-1;for (int i = root; i >=0; i--) {BuildHeap(ints, length, i);}//取值，把根結(jié)點(diǎn)元素和最后一個元素交換for (int i = 0; i <ints.length; i++) {swap(ints,0,length);length--;BuildHeap(ints,length,0);}System.out.println(Arrays.toString(ints));}//建立大根堆public static void BuildHeap(int arr[],int length,int root){int leftcode=root*2+1;int rightcode=root*2+2;int max=root;if(leftcode<length&&arr[leftcode]>=arr[max]){max=leftcode;}if(rightcode<length&&arr[rightcode]>=arr[max]){max=rightcode;}if (max!=root) {swap(arr,max,root);//調(diào)整完之后，可能會影響到下面的子樹，需再次調(diào)整BuildHeap(arr,length,max);}}private static void swap(int[] arr, int i, int j) {int t=arr[i];arr[i]=arr[j];arr[j]=t;} }

二、時間復(fù)雜度的計算

注意：這里計算都是以完滿二叉樹進(jìn)行計算的。

1、建堆

建堆的過程都是從倒數(shù)第二層最右邊的節(jié)點(diǎn)開始，每個節(jié)點(diǎn)調(diào)整位置花費(fèi)的時間復(fù)雜度是O(1),為了方便后面的計算，統(tǒng)計就說是執(zhí)行1次；然后是倒數(shù)第三層，這一層每個節(jié)點(diǎn)也需要執(zhí)行1次，但是因?yàn)檎{(diào)整后會影響到它的后面的節(jié)點(diǎn)，所以每個節(jié)點(diǎn)還需執(zhí)行1次（這個次數(shù)取決于你的代碼怎么寫，非常關(guān)鍵），這里非常關(guān)鍵。

int max=root; if(leftcode<length&&arr[leftcode]>=arr[max]){max=leftcode; }if(rightcode<length&&arr[rightcode]>=arr[max]){max=rightcode; } if (max!=root) {swap(arr,max,root)//調(diào)整完之后，可能會影響到下面的子樹，需再次調(diào)整BuildHeap(arr,length,max); }

上面的代碼是調(diào)整節(jié)點(diǎn)位置的過程，我們發(fā)現(xiàn)，這種代碼調(diào)整之后的結(jié)果是：**父節(jié)點(diǎn)最后只和它的左孩子節(jié)點(diǎn)或右孩子節(jié)點(diǎn)的其中一個發(fā)生了交換，**所以倒數(shù)第三層每個節(jié)點(diǎn)的在調(diào)整位置的時候，每個節(jié)點(diǎn)只會影響到它的右子樹或者左子樹的結(jié)構(gòu)中的一個，所以執(zhí)行1次。如果這里的代碼采用的是父節(jié)點(diǎn)先和左孩子結(jié)點(diǎn)比較交換然后再和右孩子節(jié)點(diǎn)比較交換的寫法，那它最后時間復(fù)雜度計算出來的結(jié)果就是nlogn；我們是以最優(yōu)的算法來計算的。
我們以三層結(jié)構(gòu)的完滿二叉樹舉例來推導(dǎo)一下計算公式

所以最后推導(dǎo)出來的公式就是：

S=[2^(k-1)+2^(k-1)*0]+[2^(k-2)+2^(k-2)*1]+[2^(k-3)+2^(k-3)*2]+......+[2^0+2^0*(k-1)] 化簡后得:S=2^(k-1)*1+2^(k-2)*2+2^(k-3)*3+.......+2^0*k;S=2^0*k+2^1*(k-1)+......+2^(k-2)*2+2^(k-1)*1; (1) 使用等比數(shù)列求和中的錯位相減法，兩邊同乘以2，得:2S=2^1*k+2^2*(k-1)+......+2^(k-1)*2+2^k*1; (2) (2)式-(1)式可得:S=-2^0*k+2^1+2^2+2^3+.......+2^(k-1)+2^k; 使用等比數(shù)列求和公式可得:S=2^(k+1)-k-2;

所以建堆的總執(zhí)行次數(shù)就是：S=2^(k+1)-k-2
完滿二叉樹的節(jié)點(diǎn)個數(shù)是2的整次冪減1，所以2^k-1=節(jié)點(diǎn)個數(shù)n，所以高度k=log(n+1);
把k帶入S中可得：S=2^(log(n+1)+1)-log(n+1)-2,化簡得S=2n-log(n+1)；
所以建堆的時間復(fù)雜度為O(n);

2、取值后重新調(diào)整堆

取值每次取的都是堆頂元素，取完重新調(diào)整的次數(shù)都是k次，時間復(fù)雜度就是也就是logn，而循環(huán)要執(zhí)行n次，所以取值后重新調(diào)整堆得時間復(fù)雜度就是O(nlogn);

綜上所述，堆排序的時間復(fù)雜度就是O(n(logn+1))就是O(nlogn);

完全都是個人理解，網(wǎng)上搜了好多，自己都沒看的太懂，后來自己摸索著搞了搞，哪里有問題還請指正。

總結(jié)

以上是生活随笔為你收集整理的堆排序时间复杂度的计算过程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。