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

深入解析堆排序的算法思想及Java代碼的實現(xiàn)演示

 更新時間:2016年06月08日 11:22:42   作者:黃儀標  
堆排序基于二叉堆結(jié)構(gòu)即完全二叉樹,可利用最大堆和最小堆的組建方式來進行排序,這里就來深入解析堆排序的算法思想及Java代碼的實現(xiàn)演示

一、基礎(chǔ)知識
我們通常所說的堆是指二叉堆,二叉堆又稱完全二叉樹或者叫近似完全二叉樹。二叉堆又分為最大堆和最小堆。
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法,它是選擇排序的一種??梢岳脭?shù)組的特點快速定位指定索引的元素。數(shù)組可以根據(jù)索引直接獲取元素,時間復(fù)雜度為O(1),也就是常量,因此對于取值效率極高。
最大堆的特性如下:

  • 父結(jié)點的鍵值總是大于或者等于任何一個子節(jié)點的鍵值
  • 每個結(jié)點的左子樹和右子樹都是一個最大堆

最小堆的特性如下:

  • 父結(jié)點的鍵值總是小于或者等于任何一個子節(jié)點的鍵值
  • 每個結(jié)點的左子樹和右子樹都是一個最小堆

二、算法思想
1.最大堆的算法思想是:
先將初始的R[0…n-1]建立成最大堆,此時是無序堆,而堆頂是最大元素
再將堆頂R[0]和無序區(qū)的最后一個記錄R[n-1]交換,由此得到新的無序區(qū)R[0…n-2]和有序區(qū)R[n-1],且滿足R[0…n-2].keys ≤ R[n-1].key
由于交換后,前R[0…n-2]可能不滿足最大堆的性質(zhì),因此再調(diào)整前R[0…n-2]為最大堆,直到只有R[0]最后一個元素才調(diào)整完成。
最大堆排序完成后,其實是升序序列,每次調(diào)整堆都是要得到最大的一個元素,然后與當(dāng)前堆的最后一個元素交換,因此最后所得到的序列是升序序列。
2.最小堆的算法思想是:
先將初始的R[0…n-1]建立成最小堆,此時是無序堆,而堆頂元素是最小的元素
再將堆頂R[0]與無序區(qū)的最后一個R[n-1]交換,由此得到新的無序堆R[0…n-2]和有序堆R[n-1],且滿足R[0…n-2].keys >= R[n-1].key
由于交換后,前R[0…n-2]可能不滿足最小堆的性質(zhì),因此再調(diào)整前R[0…n-2]為最小堆,直到只有R[0]最后一個元素才調(diào)整完成
最小堆排序完成后,其實是降序序列,每次調(diào)整堆都是要得到最小的一個元素,然后與當(dāng)前無序堆的最后一個元素交換,所以所得到的序列是降序的。
提示:堆排序的過程,其實就是不斷地擴大有序區(qū),然后不斷地縮小無序區(qū),直到只有有序區(qū)的過程。

三、排序過程分析
因為算法比較抽象,這里直接通過舉個小例子來說明堆排序的過程是如何的。下面我們用這個無序序列采用最大堆的進行堆排序,所得到的序列就是升序序列(ASC)。
無序序列:89,-7,999,-89,7,0,-888,7,-7
第一步:初始化建成最大堆:

201668111619654.png (800×577)

第二步:將堆頂最大元素999與無序區(qū)的最后一個元素交換,使999成為有序區(qū)。交換后,-7成為堆頂,由于-7并不是無序區(qū)中最大的元素,因此需要調(diào)整無序區(qū),使無序區(qū)中最大值89成為堆頂,所以-7與89交換。交換后導(dǎo)致89的右子樹不滿足最大堆的性質(zhì),因此要對右子樹調(diào)整成最大堆,所以-7要與0交換,如下圖:

201668111727507.jpg (800×301)

從圖中看到,當(dāng)-7成89交換后,堆頂是最大元素了,但是-7的左孩子是0,右孩子是-888,由于-7<0,導(dǎo)致-7這個結(jié)點不滿足堆的性質(zhì),因此需要調(diào)整它。所以,0與-7交換。
然后不斷重復(fù)著第二步的過程,直到全部成為有序區(qū)。
最后:所得到的是升序序列

201668111750215.jpg (800×606)

四、時間復(fù)雜度
堆排序的時間,主要由建立初始堆和反復(fù)調(diào)整堆這兩部分的時間開銷構(gòu)成.由于堆排序是不穩(wěn)定的,它得扭到的時間復(fù)雜度會根據(jù)實際情況較大,因此只能取平均時間復(fù)雜度。
平均時間復(fù)雜度為:O( N * log2(N) )
堆排序耗時的操作有:初始堆 + 反復(fù)調(diào)整堆,時間復(fù)雜度如下:
1.初始建堆:每個父節(jié)點會和左右子節(jié)點進行最多2次比較和1次交換,所以復(fù)雜度跟父節(jié)點個數(shù)有關(guān)。根據(jù)2x <= n(x為n個元素可以折半的次數(shù),也就是父節(jié)點個數(shù)),得出x = log2n。即O ( log2n )
2.反復(fù)調(diào)整堆:由于初始化堆過程中,會記錄數(shù)組比較結(jié)果,所以堆排序?qū)υ蛄械臄?shù)組順序并不敏感,最好情況和最壞情況差不多。需要抽取 n-1 次堆頂元素,每次取堆頂元素都需要重建堆(O(重建堆) < O(初始堆))。所以小于 O(n-1) * O(log2n)
使用建議:
由于初始化堆需要比較的次數(shù)較多,因此,堆排序比較適合于數(shù)據(jù)量非常大的場合(百萬數(shù)據(jù)或更多)。由于高效的快速排序是基于遞歸實現(xiàn)的,所以在數(shù)據(jù)量非常大時會發(fā)生堆棧溢出錯誤。

五、Java示例代碼

public class HeapSort{
 private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12,
   17,34,11};

 public static void main(String[] args){
  buildMaxHeapify(sort);
  heapSort(sort);
  print(sort);
 }

 private static void buildMaxHeapify(int[] data){
//沒有子節(jié)點的才需要創(chuàng)建最大堆,從最后一個的父節(jié)點開始
  int startIndex=getParentIndex(data.length-1);
//從尾端開始創(chuàng)建最大堆,每次都是正確的堆
  for(int i=startIndex;i>=0;i--){
   maxHeapify(data,data.length,i);
  }
 }

 /**
  *創(chuàng)建最大堆
  *
  *@paramdata
  *@paramheapSize需要創(chuàng)建最大堆的大小,一般在sort的時候用到,因為最多值放在末尾,末尾就不再歸入最大堆了
  *@paramindex當(dāng)前需要創(chuàng)建最大堆的位置
  */
 private static void maxHeapify(int[] data,int heapSize,int index){
//當(dāng)前點與左右子節(jié)點比較
  int left=getChildLeftIndex(index);
  int right=getChildRightIndex(index);

  int largest=index;
  if(left<heapSize&&data[index]<data[left]){
   largest=left;
  }
  if(right<heapSize&&data[largest]<data[right]){
   largest=right;
  }
//得到最大值后可能需要交換,如果交換了,其子節(jié)點可能就不是最大堆了,需要重新調(diào)整
  if(largest!=index){
   int temp=data[index];
   data[index]=data[largest];
   data[largest]=temp;
   maxHeapify(data,heapSize,largest);
  }
 }

 /**
  *排序,最大值放在末尾,data雖然是最大堆,在排序后就成了遞增的
  *
  *@paramdata
  */
 private static void heapSort(int[] data){
//末尾與頭交換,交換后調(diào)整最大堆
  for(int i=data.length-1;i>0;i--){
   int temp=data[0];
   data[0]=data[i];
   data[i]=temp;
   maxHeapify(data,i,0);
  }
 }

 /**
  *父節(jié)點位置
  *
  *@paramcurrent
  *@return
  */
 private static int getParentIndex(int current){
  return(current-1)>>1;
 }

 /**
  *左子節(jié)點position注意括號,加法優(yōu)先級更高
  *
  *@paramcurrent
  *@return
  */
 private static int getChildLeftIndex(int current){
  return(current<<1)+1;
 }

 /**
  *右子節(jié)點position
  *
  *@paramcurrent
  *@return
  */
 private static int getChildRightIndex(int current){
  return(current<<1)+2;
 }

 private static void print(int[] data){
  int pre=-2;
  for(int i=0;i<data.length;i++){
   if(pre<(int)getLog(i+1)){
    pre=(int)getLog(i+1);
    System.out.println();
   }
   System.out.print(data[i]+"|");
  }
 }

 /**
  *以2為底的對數(shù)
  *
  *@paramparam
  *@return
  */
 private static double getLog(double param){
  return Math.log(param)/Math.log(2);
 }
}

相關(guān)文章

  • Spring體系的各種啟動流程詳解

    Spring體系的各種啟動流程詳解

    這篇文章主要給大家介紹了關(guān)于Spring體系的各種啟動流程,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-03-03
  • springBoot集成Elasticsearch 報錯 Health check failed的解決

    springBoot集成Elasticsearch 報錯 Health check failed的解決

    這篇文章主要介紹了springBoot集成Elasticsearch 報錯 Health check failed的解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • 詳解Nacos中注冊中心和配置中心的實現(xiàn)

    詳解Nacos中注冊中心和配置中心的實現(xiàn)

    Spring?Cloud?Alibaba?是阿里巴巴提供的一站式微服務(wù)開發(fā)解決方案。而?Nacos?作為?Spring?Cloud?Alibaba?的核心組件之一,提供了兩個非常重要的功能:注冊中心和配置中心,我們今天來了解和實現(xiàn)一下二者
    2022-08-08
  • Maven默認中央倉庫(settings.xml 配置詳解)

    Maven默認中央倉庫(settings.xml 配置詳解)

    這篇文章主要介紹了Maven默認中央倉庫(settings.xml 配置詳解),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-12-12
  • 詳解java_ 集合綜合案例:斗地主

    詳解java_ 集合綜合案例:斗地主

    這篇文章主要介紹了java_ 集合綜合案例:斗地主,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-04-04
  • LeetCode程序員面試題之遞歸乘法

    LeetCode程序員面試題之遞歸乘法

    在Java中,遞歸乘法是一種簡單而有效的方法,可以用來計算兩個數(shù)字的乘積。它的基本思想是:如果第一個數(shù)字是0,則乘積為0;如果第一個數(shù)字是1,則乘積為第二個數(shù)字;其他情況,則通過將第一個數(shù)字減1,并將第二個數(shù)字與自身相乘,來實現(xiàn)遞歸乘法。
    2023-02-02
  • java實現(xiàn)解析json復(fù)雜數(shù)據(jù)的方法詳解

    java實現(xiàn)解析json復(fù)雜數(shù)據(jù)的方法詳解

    這篇文章主要為大家詳細介紹了java如何實現(xiàn)解析json復(fù)雜數(shù)據(jù),文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以學(xué)習(xí)一下
    2024-01-01
  • java GUI編程之paint繪制操作示例

    java GUI編程之paint繪制操作示例

    這篇文章主要介紹了java GUI編程之paint繪制操作,結(jié)合實例形式詳細分析了java GUI編程paint繪制相關(guān)操作技巧與使用注意事項,需要的朋友可以參考下
    2020-01-01
  • SpringMVC中如何獲取@PathVariable的值

    SpringMVC中如何獲取@PathVariable的值

    這篇文章主要介紹了SpringMVC中如何獲取@PathVariable的值,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-10-10
  • java this的應(yīng)用方法解析

    java this的應(yīng)用方法解析

    這篇文章主要介紹了java this的應(yīng)用方法解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-10-10

最新評論