程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> JAVA算法起步之堆排序實例

JAVA算法起步之堆排序實例

編輯:關於JAVA

JAVA算法起步之堆排序實例。本站提示廣大學習愛好者:(JAVA算法起步之堆排序實例)文章只能為提供參考,不一定能成為您想要的結果。以下是JAVA算法起步之堆排序實例正文


進修堆排序,起首須要明確堆的概念,堆是一個數組。可以近似當作完整二叉樹的數組存儲方法。然則跟他還有其他的性質,就是相似於二叉排序樹。有最年夜堆跟最小堆之分,最年夜堆是指根節點的值都年夜於子節點的值,而最小堆的是根節點的值小於其子節點的值。堆排序普通用的是最年夜堆,而最小堆可以結構優先隊列。堆外面有一個辦法是用來保護堆的性質,也就是我們上面代碼中的maxheap辦法,這是保護最年夜堆性質的辦法,第一個參數就是堆也就是數組,第二個參數是調劑堆的詳細節點地位,能夠這個節點的值不相符最年夜堆的性質,那末這個值得地位就作為參數,而size實際上是堆內現實存儲的有用元素個數。能夠數組的長度就是堆內現實存儲的元素個數,然則紛歧定一切的數據我們都須要停止構建最年夜堆。算法導論中說的獲得左子結點是2xi然則我們數組是從0開端計數的,所以左子結點就成了2xi+1,buildheap就是構建一個最年夜堆,我們去2分之長度的緣由是,這些點的子節點都是葉子節點,所以我們經由過程從下向長進行排序來構建一個最年夜堆。包管了我們堆內一切節點都知足最年夜堆性質。最初堆排序就是把第一個節點掏出來,將剩下的節點再停止堆排序,再掏出根節點。如許包管我們每次掏出都是最年夜值。

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]);
  }
 }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved