java實(shí)現(xiàn)堆排序以及時(shí)間復(fù)雜度的分析

更新時(shí)間：2021年12月10日 09:41:59 作者：朱季謙

本文主要介紹了java實(shí)現(xiàn)堆排序以及時(shí)間復(fù)雜度，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

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

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

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

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

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

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

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

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

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

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

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

?

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

我們把根節(jié)點(diǎn)和樹(shù)的最后一個(gè)葉子節(jié)點(diǎn)進(jìn)行交換即讓數(shù)組的第一個(gè)數(shù)和最后一個(gè)數(shù)交換，交換后讓最后一個(gè)數(shù)保持位置不再變化，我們?cè)僮屍渌?jié)點(diǎn)再進(jìn)行維護(hù)大頂堆，因?yàn)榇藭r(shí)根節(jié)點(diǎn)是比子節(jié)點(diǎn)小的，重復(fù)以上操作直到需要根節(jié)點(diǎn)和他本身進(jìn)行交換時(shí)排序完成

排序流程圖如下：

?

代碼如下：

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é)果如下：

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

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

您可能感興趣的文章: