完全二叉樹：從上到下，從左到右，每層的節(jié)點都是滿的，最下邊一層所有的節(jié)點都是連續(xù)集中在最左邊。

二叉樹的特點就是左子節(jié)點是父節(jié)點索引值的2倍加一，右子節(jié)點是父節(jié)點索引值的2倍加二

堆分為兩種：大頂堆和小頂堆

? ? ? ? 大頂堆：在完全二叉樹基礎(chǔ)上，每個節(jié)點的值都大于或等于其左右子節(jié)點的值

? ? ? ? 小頂堆：在完全二叉樹基礎(chǔ)上，每個節(jié)點的值都大于或等于其左右子節(jié)點的值

堆排序就是根據(jù)先構(gòu)建好的大頂堆或小頂堆進行排序的。

怎么構(gòu)建大頂堆：

? ? ? ? 假如一個數(shù)組是：int[] arr= {3,5,7,9,1,2,4,6,8,11,10};它的完全二叉樹形狀如下圖所示：

紅色數(shù)字的是節(jié)點在數(shù)組中的索引值，它們之間的關(guān)系就是左子節(jié)點是父節(jié)點索引值的2倍加一，右子節(jié)點是父節(jié)點索引值的2倍加二

?我們想把它構(gòu)建成大頂堆就從二叉樹最下面一層開始也就是從最后一個數(shù)組開始，先比較左右子樹，找到最大的一個，用最大的和父節(jié)點進行比較如果子節(jié)點大就進行交換，交換結(jié)束后再比較此層左邊的左右和父子節(jié)點進行交換。也就是從最下一層開始，從右到左開始比較，此層比較完進入上一層再從右到左開始比較以此循環(huán)。當(dāng)?shù)竭_上一層時會有一個問題就是如果換下來的父節(jié)點比子節(jié)點小我們還需要往下進行交換，我們就需要對它進行維護。

上面數(shù)組的例子按順序構(gòu)建的大頂堆如下圖所示：

?

?

?

?

?構(gòu)建好的大頂堆的根節(jié)點總是最大的，我們根據(jù)這個特點進行排序。

我們把根節(jié)點和樹的最后一個葉子節(jié)點進行交換即讓數(shù)組的第一個數(shù)和最后一個數(shù)交換，交換后讓最后一個數(shù)保持位置不再變化，我們再讓其他節(jié)點再進行維護大頂堆，因為此時根節(jié)點是比子節(jié)點小的，重復(fù)以上操作直到需要根節(jié)點和他本身進行交換時排序完成

排序流程圖如下：

?

?

?

?

?

?

?

?

?

代碼如下：

public class heapsort {
	public static void main(String[] args) {
		int[] arr= {3,5,7,9,1,2,4,6,8,11,10};
		for(int p=arr.length-1;p>=0;p--) {
			adjustheap(arr,p,arr.length);
		}
		heapsort(arr);
		System.out.println(Arrays.toString(arr));
	}
 
	public static void heapsort(int[] arr) {
		for(int i=arr.length-1;i>=0;i--) {
			int temp=arr[i];
			arr[i]=arr[0];
			arr[0]=temp;
			adjustheap(arr, 0, i);
		}
		
	}
 
	public static void adjustheap(int[] arr, int p, int length) {
		int temp=arr[p];
		int left=p*2+1;
		while(left<length) {
			if(left+1<length&&arr[left]<arr[left+1]) {
				left++;
			}
			if(temp>arr[left]) {
				break;
			}
			arr[p]=arr[left];
			p=left;
			left=left*2+1;
			
		}
		arr[p]=temp;
	}

?輸出結(jié)果如下：

?時間復(fù)雜度：構(gòu)建大頂堆的時間復(fù)雜度是O（nlogn）,n是main方法里的for循環(huán)，logn是構(gòu)建大頂堆的方法的時間復(fù)雜度，排序的時間復(fù)雜度也是O（nlogn），所以堆排序的時間復(fù)雜度是O（nlogn）+O（nlogn）,也就是O（logn）

到此這篇關(guān)于java實現(xiàn)堆排序以及時間復(fù)雜度的分析的文章就介紹到這了,更多相關(guān)java 堆排序及時間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論