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

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

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

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

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

• JAVA
• 堆排序

相關(guān)文章

• 

  springboot實現(xiàn)定時器(一看即會,非常簡單)

  這篇文章主要介紹了springboot實現(xiàn)定時器(一看即會,非常簡單),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

  2023-12-12
• 

  SpringBoot處理JSON數(shù)據(jù)方法詳解

  這篇文章主要介紹了SpringBoot整合Web開發(fā)中Json數(shù)據(jù)處理，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

  2022-10-10
• 

  JAVA中關(guān)于Long類型返回前端精度丟失問題處理辦法

  這篇文章主要介紹了后端JavaBean的id屬性從Long類型改為雪花算法后出現(xiàn)的精度丟失問題,解決方案包括將id字段類型改為字符串或使用Jackson序列化方式,需要的朋友可以參考下

  2024-11-11
• 

  java實現(xiàn)人工智能化屏幕監(jiān)控窗口

  這篇文章主要為大家詳細(xì)介紹了java實現(xiàn)人工智能化屏幕監(jiān)控窗口，具有一定的參考價值，感興趣的小伙伴們可以參考一下

  2018-09-09
• 

  Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測試分析示例詳解

  這篇文章主要為大家介紹了Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測試分析示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

  2023-01-01
• 

  Java實現(xiàn)人機(jī)猜拳游戲

  這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)人機(jī)猜拳游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

  2020-07-07
• 

  mybatis寫xml時數(shù)字類型千萬別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解

  這篇文章主要介紹了mybatis寫xml時數(shù)字類型千萬別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

  2020-09-09
• 

  詳細(xì)總結(jié)IDEA中打jar包的兩種方式

  發(fā)現(xiàn)有很多小伙伴都不會用IDEA打jar包,今天給大家詳細(xì)總結(jié)了兩種IDEA打jar包的方式,對正在學(xué)習(xí)IDEA使用的小伙伴很有幫助,需要的朋友可以參考下

  2021-05-05
• 

  Java Web監(jiān)聽器如何實現(xiàn)定時發(fā)送郵件

  這篇文章主要介紹了Java Web監(jiān)聽器如何實現(xiàn)定時發(fā)送郵件,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

  2020-12-12
• 

  java使用FastJson解析Json數(shù)據(jù)

  本篇文章主要介紹了java使用FastJson解析Json數(shù)據(jù)，fastjson 是一個性能極好的用 Java 語言實現(xiàn)的 JSON 解析器和生成器，有興趣的可以了解一下。

  2017-02-02

最新評論