欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

在Java中實(shí)現(xiàn)堆排序的步驟詳解

 更新時(shí)間:2024年12月31日 08:31:24   作者:碼農(nóng)老起  
堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法,堆是一種特殊的完全二叉樹(shù),堆排序利用堆的性質(zhì)通過(guò)一系列操作將數(shù)組元素按升序或降序排列,本文給大家介紹了如何在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實(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-06
  • Java使用ByteArrayOutputStream 和 ByteArrayInputStream 避免重復(fù)讀取配置文件的方法

    Java使用ByteArrayOutputStream 和 ByteArrayInputStream 避免重復(fù)讀取配置文

    這篇文章主要介紹了Java使用ByteArrayOutputStream 和 ByteArrayInputStream 避免重復(fù)讀取配置文件的方法,需要的朋友可以參考下
    2015-12-12
  • Java防鎖屏小程序代碼實(shí)例

    Java防鎖屏小程序代碼實(shí)例

    這篇文章主要介紹了Java防鎖屏小程序代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-09-09
  • Eclipse中maven異常Updating Maven Project的統(tǒng)一解決方案

    Eclipse中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é))

    這篇文章主要介紹了幾個(gè)好用Maven鏡像倉(cāng)庫(kù)地址(小結(jié)),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-09-09
  • SpringBoot  jdbctemplate使用方法解析

    SpringBoot jdbctemplate使用方法解析

    這篇文章主要介紹了SpringBoot jdbctemplate使用方法解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-05-05
  • Spring注解配置AOP導(dǎo)致通知執(zhí)行順序紊亂解決方案

    Spring注解配置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

    這篇文章主要介紹了淺談java字符串比較到底應(yīng)該用==還是equals,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-12-12
  • SpringBoot+微信小程序?qū)崿F(xiàn)文件上傳與下載功能詳解

    SpringBoot+微信小程序?qū)崿F(xiàn)文件上傳與下載功能詳解

    這篇文章主要為大家介紹了SpringBoot整合微信小程序?qū)崿F(xiàn)文件上傳與下載功能,文中的實(shí)現(xiàn)步驟講解詳細(xì),快跟隨小編一起學(xué)習(xí)一下吧
    2022-03-03
  • java 中的instanceof用法詳解及instanceof是什么意思(推薦)

    java 中的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

最新評(píng)論