java堆排序原理與實現(xiàn)方法分析

更新時間：2018年12月26日 11:38:38 作者：_almost_

這篇文章主要介紹了java堆排序原理與實現(xiàn)方法,結合實例形式分析了java堆排序的相關原理、實現(xiàn)方法與操作注意事項,需要的朋友可以參考下

本文實例講述了java堆排序原理與實現(xiàn)方法。分享給大家供大家參考，具體如下：

堆是一個數(shù)組，被看成一個近似完全二叉樹。

舉例說明：

堆的性質：

1.已知元素在數(shù)組中的序號為i

其父節(jié)點的序號為 i/2的整數(shù)
其左孩子節(jié)點的序號為2*i
其右孩子節(jié)點的序號為2*i+1

2.堆分為最大堆和最小堆

在最大堆中，要保證父節(jié)點的值大于等于其孩子節(jié)點的值
在最小堆中，要保證父節(jié)點的值小于等于其孩子節(jié)點的值

java實現(xiàn)堆排序

public class MyHeapSort {
  public void Heap_Sort(int[] A) {
    /**
     * 這個函數(shù)完成堆排序
     * 先構建一個最大堆
     * 將數(shù)組中第一個元素和最后一個交換，
     * 堆的長度減一
     * 在從第一個位置開始保證堆的性質調用Max_heapify()函數(shù)。
     * 這樣保證目前最大的元素在數(shù)組的最后位置。
     * 以此類推，直到最后一個元素。
     */
    Build_Max_Heap(A);
    for (int i = A.length - 1; i >= 1; i--) {
      int temp = A[0];
      A[0] = A[i];
      A[i] = temp;
      Max_heapify(A, 0, i);
    }
  }
  public void Build_Max_Heap(int[] A) {
    /**
     * 這個函數(shù)用來構建堆
     * A:待排序的數(shù)組
     * （for循環(huán)中i的值從數(shù)組長度的一般開始取，是因為完全二叉樹的性質，
     * 一半的節(jié)點葉根節(jié)點所以從葉節(jié)點開始向上遍歷來保證堆的性質）
     */
    for (int i = A.length/2; i >= 0; i--) {
      Max_heapify(A, i, A.length);
    }
  }
  public void Max_heapify(int[] A, int i, int heap_size) {
    /**這個函數(shù)用來維護堆的性質，
     * 保證以序號為i的元素為根節(jié)點的子樹中，父節(jié)點的值大于其孩子節(jié)點的值。
     * A:待排序數(shù)組
     * i：在數(shù)組A中的序號
     * heap_size:堆的大小
     */
    int largest = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    if (l < heap_size && A[l] > A[i]) largest = l;
    if (r < heap_size && A[r] > A[largest]) largest = r;
    if (largest != i) {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
      Max_heapify(A, largest, heap_size);
    }
  }
  public static void main(String[] args) throws Exception {
    System.out.println("腳本之家測試結果：");
    int[] a = new int[]{1,3,2,5,34,23,44,15,67,45};
    new MyHeapSort().Heap_Sort(a);
    for (int x : a) System.out.println(x);
  }
}

代碼中例子的運行結果：