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

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

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

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

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

舉例說明：

堆的性質(zhì)：

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

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

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

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

java實(shí)現(xiàn)堆排序

public class MyHeapSort {
  public void Heap_Sort(int[] A) {
    /**
     * 這個(gè)函數(shù)完成堆排序
     * 先構(gòu)建一個(gè)最大堆
     * 將數(shù)組中第一個(gè)元素和最后一個(gè)交換，
     * 堆的長度減一
     * 在從第一個(gè)位置開始保證堆的性質(zhì)調(diào)用Max_heapify()函數(shù)。
     * 這樣保證目前最大的元素在數(shù)組的最后位置。
     * 以此類推，直到最后一個(gè)元素。
     */
    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) {
    /**
     * 這個(gè)函數(shù)用來構(gòu)建堆
     * A:待排序的數(shù)組
     * （for循環(huán)中i的值從數(shù)組長度的一般開始取，是因?yàn)橥耆鏄涞男再|(zhì)，
     * 一半的節(jié)點(diǎn)葉根節(jié)點(diǎn)所以從葉節(jié)點(diǎn)開始向上遍歷來保證堆的性質(zhì)）
     */
    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) {
    /**這個(gè)函數(shù)用來維護(hù)堆的性質(zhì)，
     * 保證以序號(hào)為i的元素為根節(jié)點(diǎn)的子樹中，父節(jié)點(diǎn)的值大于其孩子節(jié)點(diǎn)的值。
     * A:待排序數(shù)組
     * i：在數(shù)組A中的序號(hào)
     * 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("腳本之家測試結(jié)果：");
    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);
  }
}

代碼中例子的運(yùn)行結(jié)果：