JAVA算法起步之堆排序?qū)嵗?/h1>

 更新時間：2014年02月10日 15:17:15   作者：  

這篇文章主要介紹了JAVA算法起步之堆排序?qū)嵗?需要的朋友可以參考下

學(xué)習(xí)堆排序，首先需要明白堆的概念，堆是一個數(shù)組。可以近似當(dāng)做完全二叉樹的數(shù)組存儲方式。但是跟他還有其他的性質(zhì)，就是類似于二叉排序樹。有最大堆跟最小堆之分，最大堆是指根節(jié)點(diǎn)的值都大于子節(jié)點(diǎn)的值，而最小堆的是根節(jié)點(diǎn)的值小于其子節(jié)點(diǎn)的值。堆排序一般用的是最大堆，而最小堆可以構(gòu)造優(yōu)先隊(duì)列。堆里面有一個方法是用來維護(hù)堆的性質(zhì)，也就是我們下面代碼中的maxheap方法，這是維護(hù)最大堆性質(zhì)的方法，第一個參數(shù)就是堆也就是數(shù)組，第二個參數(shù)是調(diào)整堆的具體節(jié)點(diǎn)位置，可能這個節(jié)點(diǎn)的值不符合最大堆的性質(zhì)，那么這個值得位置就作為參數(shù)，而size其實(shí)是堆內(nèi)實(shí)際存儲的有效元素個數(shù)?？赡軘?shù)組的長度就是堆內(nèi)實(shí)際存儲的元素個數(shù)，但是不一定所有的數(shù)據(jù)我們都需要進(jìn)行構(gòu)建最大堆。算法導(dǎo)論中說的得到左子結(jié)點(diǎn)是2xi但是我們數(shù)組是從0開始計(jì)數(shù)的，所以左子結(jié)點(diǎn)就成了2xi+1，buildheap就是構(gòu)建一個最大堆，我們?nèi)?分之長度的原因是，這些點(diǎn)的子節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，所以我們通過從下向上進(jìn)行排序來構(gòu)建一個最大堆。保證了我們堆內(nèi)所有節(jié)點(diǎn)都滿足最大堆性質(zhì)。最后堆排序就是把第一個節(jié)點(diǎn)取出來，將剩下的節(jié)點(diǎn)再進(jìn)行堆排序，再取出根節(jié)點(diǎn)。這樣保證我們每次取出都是最大值。

復(fù)制代碼 代碼如下:

public class HeapSort {
 private int getLeft(int i){
  return 2*i+1;
 }
 private int getRight(int i){
  return 2*i+2;
 }
 public void maxheap(int[] heap,int loc,int size){
  int l=getLeft(loc);
  int r=getRight(loc);
  int largest=loc;
  if(l<size&&heap[l]>heap[loc]){
   largest=l;
  }
  if (r<size&&heap[r]>heap[largest]) {
   largest=r;
  }
  if(largest!=loc){
   int cache=heap[loc];
   heap[loc]=heap[largest];
   heap[largest]=cache;
   maxheap(heap, largest, size);
  }
 }
 public void buildheap(int[] heap){
  for(int i=heap.length/2;i>=0;i--){
   maxheap(heap, i, heap.length);
  }
 }
 public void sort(int[] heap){
  buildheap(heap);
  for(int i=heap.length-1;i>1;i--){
   int cache=heap[0];
    heap[0]=heap[i];
    heap[i]=cache;
   maxheap(heap, 0,i );
  }
  int cache=heap[0];
   heap[0]=heap[1];
   heap[1]=cache;

 }

 public static void main(String[] args) {
  int[] heap=new int[]{4,1,5,3,7,12,65,7};
  HeapSort hs=new HeapSort();
  hs.sort(heap);
  for (int i = 0; i < heap.length; i++) {
   System.out.println(heap[i]);
  }
 }
}

您可能感興趣的文章:

• Java算法之?dāng)?shù)組冒泡排序代碼實(shí)例講解
• Java算法之串的簡單處理
• Java算法實(shí)現(xiàn)調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)之前的講解
• Java算法實(shí)現(xiàn)楊輝三角的講解
• Java算法之冒泡排序?qū)嵗a
• Java算法之最長公共子序列問題(LCS)實(shí)例分析
• java算法實(shí)現(xiàn)紅黑樹完整代碼示例
• Java算法之堆排序代碼示例
• java算法之二分查找法的實(shí)例詳解
• java算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼
• java算法實(shí)現(xiàn)預(yù)測雙色球中獎號碼
• Java算法之遞歸算法計(jì)算階乘
• JAVA算法起步之插入排序?qū)嵗?/a>
• JAVA算法起步之快速排序?qū)嵗?/a>
• 關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
• Java算法之時間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算

• JAVA
• 堆排序

相關(guān)文章

• 

  SpringBoot如何配置獲取request中body的json格式參數(shù)

  這篇文章主要介紹了SpringBoot如何配置獲取request中body的json格式參數(shù)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

  2022-06-06
• 

  Spring中@Validated和@Valid區(qū)別淺析

  @Valid是javax.validation里的,?@Validated是@Valid?的一次封裝,是Spring提供的校驗(yàn)機(jī)制使用,下面這篇文章主要給大家介紹了關(guān)于Spring中@Validated和@Valid區(qū)別的相關(guān)資料,需要的朋友可以參考下

  2022-04-04
• 

  Java數(shù)據(jù)類型轉(zhuǎn)換實(shí)例解析

  這篇文章主要介紹了Java數(shù)據(jù)類型轉(zhuǎn)換實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

  2019-11-11
• 

  SpringBoot自定義路由覆蓋實(shí)現(xiàn)流程詳解

  這篇文章主要介紹了SpringBoot自定義路由覆蓋實(shí)現(xiàn)流程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧

  2023-01-01
• 

  Java時間處理第三方包Joda?Time使用詳解

  這篇文章主要為大家介紹了Java時間處理第三方包Joda?Time使用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

  2022-07-07
• 

  springboot使用Logback把日志輸出到控制臺或輸出到文件

  這篇文章給大家介紹springboot項(xiàng)目使用日志工具Logback把日志不僅輸出到控制臺，也可以輸出到文件的操作方法，本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友參考下吧

  2020-10-10
• 

  Java實(shí)現(xiàn)擲骰子控制臺和窗體兩種方法

  這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)擲骰子控制臺和窗體兩種方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

  2021-08-08
• 

  JAVA線程池專題（概念和作用）

  這篇文章主要介紹了Java線程池的概念和作用，文中講解非常詳細(xì)，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下

  2020-06-06
• 

  java 獲取mac地址的兩種方法(推薦)

  下面小編就為大家?guī)硪黄猨ava 獲取mac地址的兩種方法(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

  2016-10-10
• 

  Mybatis中返回Map的實(shí)現(xiàn)

  這篇文章主要介紹了Mybatis中返回Map的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

  2021-03-03

最新評論