在Java中實(shí)現(xiàn)堆排序的步驟詳解
引言
堆排序(Heap Sort)是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法。堆是一種特殊的完全二叉樹(shù),堆排序利用堆的性質(zhì)通過(guò)一系列操作將數(shù)組元素按升序或降序排列。堆排序的時(shí)間復(fù)雜度為 O(n log n),是一種不穩(wěn)定的排序算法,且其空間復(fù)雜度為 O(1),因此在某些場(chǎng)景下非常有用。
一、堆排序的基本原理
堆排序的核心是堆(Heap)這一數(shù)據(jù)結(jié)構(gòu),堆有兩種形式:
(1)最大堆(Max-Heap):每個(gè)節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值,根節(jié)點(diǎn)的值是整個(gè)堆的最大值。
(2)最小堆(Min-Heap):每個(gè)節(jié)點(diǎn)的值小于或等于其子節(jié)點(diǎn)的值,根節(jié)點(diǎn)的值是整個(gè)堆的最小值。
堆排序一般使用最大堆來(lái)排序數(shù)組。堆排序的過(guò)程可以分為兩個(gè)主要步驟:
(1)構(gòu)建最大堆:將無(wú)序數(shù)組轉(zhuǎn)換成最大堆。
(2)排序過(guò)程:反復(fù)將堆頂元素(最大值)與當(dāng)前堆的最后一個(gè)元素交換,然后調(diào)整堆,直到堆中只剩下一個(gè)元素。
二、堆排序的實(shí)現(xiàn)步驟
(1)構(gòu)建最大堆:首先將輸入的無(wú)序數(shù)組構(gòu)造成最大堆。此時(shí)數(shù)組中的最大元素位于根節(jié)點(diǎn)。
(2)交換堆頂元素與最后一個(gè)元素:將堆頂元素與堆的最后一個(gè)元素交換,并減小堆的有效元素?cái)?shù)量。
(3)堆化:將根節(jié)點(diǎn)與其子節(jié)點(diǎn)進(jìn)行比較,調(diào)整堆的結(jié)構(gòu),使其重新滿足最大堆的性質(zhì)。
(4)重復(fù)步驟2和3:直到堆的有效元素?cái)?shù)量為1,整個(gè)數(shù)組已經(jīng)排序完成。
三、堆排序的時(shí)間復(fù)雜度和空間復(fù)雜度
(1)時(shí)間復(fù)雜度:構(gòu)建最大堆的時(shí)間復(fù)雜度是 O(n),而每次堆化的時(shí)間復(fù)雜度是 O(log n),因此總的時(shí)間復(fù)雜度為 O(n log n)。
(2)空間復(fù)雜度:堆排序是原地排序算法,因此其空間復(fù)雜度為 O(1)。四、堆排序的Java實(shí)現(xiàn)
下面是堆排序的Java實(shí)現(xiàn)代碼:
public class HeapSort { // 堆化過(guò)程,保證以i為根的子樹(shù)滿足堆的性質(zhì) private static void heapify(int[] arr, int n, int i) { int largest = i; // 初始化最大值為根節(jié)點(diǎn) int left = 2 * i + 1; // 左子節(jié)點(diǎn)的位置 int right = 2 * i + 2; // 右子節(jié)點(diǎn)的位置 // 如果左子節(jié)點(diǎn)大于根節(jié)點(diǎn) if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右子節(jié)點(diǎn)大于當(dāng)前最大值 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是根節(jié)點(diǎn),交換并繼續(xù)堆化 if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // 遞歸堆化受影響的子樹(shù) heapify(arr, n, largest); } } // 堆排序主函數(shù) public static void heapSort(int[] arr) { int n = arr.length; // 構(gòu)建最大堆 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 逐步將堆頂元素與最后一個(gè)元素交換,并調(diào)整堆 for (int i = n - 1; i >= 1; i--) { // 將堆頂元素與當(dāng)前未排序部分的最后一個(gè)元素交換 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 調(diào)整堆 heapify(arr, i, 0); } } // 打印數(shù)組 private static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr = {4, 10, 3, 5, 1}; System.out.println("Original array:"); printArray(arr); heapSort(arr); System.out.println("Sorted array:"); printArray(arr); } }
四、堆排序的工作流程
讓我們通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)理解堆排序的工作流程。
1. 構(gòu)建最大堆
假設(shè)我們有一個(gè)數(shù)組 arr = [4, 10, 3, 5, 1]。
(1)初始數(shù)組:[4, 10, 3, 5, 1]
(2)構(gòu)建最大堆的過(guò)程中,我們從 i = n/2 - 1 開(kāi)始,依次調(diào)整每個(gè)節(jié)點(diǎn),直到根節(jié)點(diǎn)。
(3)調(diào)整后的堆:[10, 5, 3, 4, 1],此時(shí)堆頂?shù)脑厥亲畲笾怠?/p>
2. 排序過(guò)程
交換堆頂元素與最后一個(gè)元素,并調(diào)整堆。
(1)第一次交換:交換堆頂和最后一個(gè)元素后,數(shù)組變?yōu)椋篬1, 5, 3, 4, 10]。然后對(duì)剩余元素進(jìn)行堆化,調(diào)整后的堆是:[5, 4, 3, 1, 10]。
(2)第二次交換:交換堆頂和倒數(shù)第二個(gè)元素,數(shù)組變?yōu)椋篬1, 4, 3, 5, 10],調(diào)整后的堆是:[4, 1, 3, 5, 10]。
(3)第三次交換:交換堆頂和倒數(shù)第三個(gè)元素,數(shù)組變?yōu)椋篬3, 1, 4, 5, 10],調(diào)整后的堆是:[3, 1, 4, 5, 10]。
(4)第四次交換:交換堆頂和倒數(shù)第四個(gè)元素,數(shù)組變?yōu)椋篬1, 3, 4, 5, 10],此時(shí)只有一個(gè)元素剩下,排序完成。
最終,數(shù)組變?yōu)樯蚺帕校篬1, 3, 4, 5, 10]。
五、堆排序的優(yōu)缺點(diǎn)
優(yōu)點(diǎn):
(1)時(shí)間復(fù)雜度穩(wěn)定:無(wú)論輸入數(shù)據(jù)如何,堆排序的時(shí)間復(fù)雜度始終為 O(n log n),不受數(shù)據(jù)分布影響。
(2)空間復(fù)雜度低:堆排序是原地排序算法,其空間復(fù)雜度為 O(1),無(wú)需額外的輔助空間。
(3)適合大數(shù)據(jù)處理:由于堆排序的時(shí)間復(fù)雜度穩(wěn)定且不依賴于數(shù)據(jù)的初始狀態(tài),它適用于大數(shù)據(jù)量的排序。
缺點(diǎn):
(1)不是穩(wěn)定排序:堆排序不保證相等元素的相對(duì)順序,因此不適用于需要穩(wěn)定排序的場(chǎng)景。
(2)常數(shù)因素較大:雖然堆排序的時(shí)間復(fù)雜度是 O(n log n),但其常數(shù)因素較大,通常比快速排序和歸并排序要慢,尤其在處理小數(shù)據(jù)集時(shí)。
六、堆排序的應(yīng)用場(chǎng)景
(1)優(yōu)先隊(duì)列實(shí)現(xiàn):堆可以用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列,特別是在需要頻繁獲取最大或最小值的場(chǎng)景中(例如,Dijkstra算法、Huffman編碼)。
(2)外部排序:當(dāng)數(shù)據(jù)量過(guò)大,不能全部加載到內(nèi)存時(shí),堆排序可以有效地對(duì)外部存儲(chǔ)的海量數(shù)據(jù)進(jìn)行排序。
總結(jié)
堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法,具有 O(n log n) 的時(shí)間復(fù)雜度和 O(1) 的空間復(fù)雜度。盡管堆排序是一個(gè)不穩(wěn)定的排序算法,但其高效性和原地排序特性使它在某些特定場(chǎng)景中非常有用,尤其是在需要頻繁訪問(wèn)最大值或最小值的應(yīng)用中。
以上就是在Java中實(shí)現(xiàn)堆排序的步驟詳解的詳細(xì)內(nèi)容,更多關(guān)于Java堆排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
使用Java實(shí)現(xiàn)KMZ和KML數(shù)據(jù)的直接解析
本文主要講解如何用JAVA語(yǔ)言,直接解析KMZ數(shù)據(jù),文章首先介紹google地圖中的KMZ和KML數(shù)據(jù),然后使用代碼的方式實(shí)現(xiàn)數(shù)據(jù)的解析,最后展示解析成果以及如何將數(shù)據(jù)轉(zhuǎn)換成空間WKT數(shù)據(jù),需要的朋友可以參考下2024-06-06Java使用ByteArrayOutputStream 和 ByteArrayInputStream 避免重復(fù)讀取配置文
這篇文章主要介紹了Java使用ByteArrayOutputStream 和 ByteArrayInputStream 避免重復(fù)讀取配置文件的方法,需要的朋友可以參考下2015-12-12Eclipse中maven異常Updating Maven Project的統(tǒng)一解決方案
今天小編就為大家分享一篇關(guān)于Eclipse中maven異常Updating Maven Project的統(tǒng)一解決方案,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-12-12幾個(gè)好用Maven鏡像倉(cāng)庫(kù)地址(小結(jié))
這篇文章主要介紹了幾個(gè)好用Maven鏡像倉(cāng)庫(kù)地址(小結(jié)),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09Spring注解配置AOP導(dǎo)致通知執(zhí)行順序紊亂解決方案
這篇文章主要介紹了Spring注解配置AOP導(dǎo)致通知執(zhí)行順序紊亂解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10淺談java字符串比較到底應(yīng)該用==還是equals
這篇文章主要介紹了淺談java字符串比較到底應(yīng)該用==還是equals,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12SpringBoot+微信小程序?qū)崿F(xiàn)文件上傳與下載功能詳解
這篇文章主要為大家介紹了SpringBoot整合微信小程序?qū)崿F(xiàn)文件上傳與下載功能,文中的實(shí)現(xiàn)步驟講解詳細(xì),快跟隨小編一起學(xué)習(xí)一下吧2022-03-03java 中的instanceof用法詳解及instanceof是什么意思(推薦)
instanceof 是 Java 的保留關(guān)鍵字。它的作用是測(cè)試它左邊的對(duì)象是否是它右邊的類(lèi)的實(shí)例,返回 boolean 的數(shù)據(jù)類(lèi)型。接下來(lái)通過(guò)本文給大家介紹java 中的instanceof用法詳解及instanceof是什么意思,需要的朋友參考下吧2017-11-11