堆排序：利用堆的特性進行排序,先將數組轉換為堆對象（最大堆或最小堆），以最大堆為例，每次heapify之后，取出堆頂（索引為0)的元素與最后一個元素交換。以后每次做同樣的事情，只是堆的長度每次-1，直到1為止（最后一個元素不需要調整)。

堆排序流程

將數組調整為堆模型

我們以最大堆為例，傳入一個無序的數組。先將其調整為堆最大堆模型，也就是最大值在第一個位置（樹的根節點）。

定義數組存儲待排序內容

public class HeapSort {private int[] elements; //堆的數組public HeapSort(int[] elements) {this.elements = elements;}}

定義heapify方法對數組調整大堆結構

  public void heapify(int curr,int size) {//1. 設置當前節點為最大節點int largest = curr;//2. 計算當前節點的左子節點，和右子節點int left = 2 * curr + 1;int right = 2 * curr + 2;// 3.1比較左子節點if (left < size && elements[left] > elements[largest]) {largest = left;}if (right < size && elements[right] > elements[largest]) {largest = right;}//交換largsetif (largest != curr) {int tmp = elements[largest];elements[largest] = elements[curr];elements[curr] = tmp;heapify(largest,size);}}

對數組使用堆排序

所謂堆排序，是我們將每次調整后的最大值（即堆的頂點即第一個元素）和最后一個元素進行調換，然后對除最后一個元素的所有元素繼續按大堆進行調整。

   public void sort() {int len = elements.length;//數組長度每輪減一，將第一個元素移到從后向前的位置。while (len>1) {for(int i = len/2-1;i>=0;i--){heapify(i, len);}swap(0,--len);}}/*** 數組中的元素交換的方法*/ public void swap(int i,int j){int t = elements[i];elements[i] = elements[j];elements[j] = t;}/*** 打印數組元素*/
public void print() {System.out.println(Arrays.toString(this.elements));
}

測試排序

    public static void main(String[] args) {int[] a = {3, 9, 2, 1, 4, 5};System.out.println("init: " + Arrays.toString(a));HeapSort hs = new HeapSort(a);hs.sort();hs.print();}