堆排序算法，基于選擇排序的思想，利用堆結(jié)構(gòu)的性質(zhì)來完成對數(shù)據(jù)的排序。

前提準備：

1. 什么是堆結(jié)構(gòu)：
   堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一科完全二叉樹結(jié)構(gòu)。它的特點是父結(jié)點的值大于（小于）兩個子結(jié)點的值（分別稱為大頂堆和小頂堆）

   
   
   堆示意圖

2. 堆結(jié)構(gòu)的性質(zhì)：
   對于第n個結(jié)點而言 --- 它的父結(jié)點下標 i = （n-1）/ 2，左子結(jié)點 left = 2n+1，右子結(jié)點 right =2n+2

結(jié)構(gòu)圖

算法基本思想：

1. 構(gòu)建堆（大頂堆或小頂堆，現(xiàn)以大頂堆為例）：

• 首先從最后一個結(jié)點開始，找到它的父結(jié)點，在父結(jié)點和父結(jié)點的左右結(jié)點中，選出最大的值，與父節(jié)點交換。
• 然后對倒數(shù)第二個結(jié)點執(zhí)行同樣的操作
• 這樣直到根結(jié)點的時候，根結(jié)點變成了所以數(shù)據(jù)中最大的值。

2. 替換根結(jié)點，重建堆：

• 將根結(jié)點與最后一個結(jié)點的數(shù)據(jù)交換，在把倒數(shù)第二個結(jié)點視為最后一個結(jié)點，重新建堆。
• 重復上述的操作。最終，數(shù)據(jù)排序完成。

代碼實現(xiàn)：

import java.util.Arrays;

/**
 * Created by noonbiteun
 * Date: 2017/7/31
 */
public class HeapSort {
    //建堆
    private static void heapConstruct(int[] arr, int last) {
        int tmp;
        for (int parent = (last - 1) / 2; parent >= 0; parent = (last-1) / 2) {
            if (2*parent+1 < last) {
                //第last個節(jié)點為右子樹
                if (arr[last - 1] < arr[last]) {
                    //大的數(shù)據(jù)往前移
                    tmp = arr[last];
                    arr[last] = arr[last - 1];
                    arr[last - 1] = tmp;
                } else {
                    last--;
                }
            }
            if (arr[parent] < arr[last]) {
                //大的數(shù)據(jù)移到父節(jié)點
                tmp = arr[last];
                arr[last] = arr[parent];
                arr[parent] = tmp;
            }
            last--;
        }
    }

    private static void sort(int[] arr) {
        int last = arr.length - 1;
        int tmp;
        System.out.println("原始順序： " + Arrays.toString(arr));
        for (int i = 0; i < arr.length; i++) {
            heapConstruct(arr, last);
            //第一個和最后一個交換
            tmp = arr[0];
            arr[0] = arr[last];
            arr[last] = tmp;
            last--;
            System.out.println("第" + i + "趟排序：" + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        //初始化數(shù)組
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * (100 + 1));
        }

        HeapSort.sort(arr);
    }
}

輸出結(jié)果：

運行結(jié)果

小結(jié)分析：

經(jīng)過兩三天的不斷學習，感覺這方面在一點點的進步，今天的這個堆排序，只看了書上寫的算法思想之后，馬上就能寫出來，感覺比前幾天對著一個冒泡排序死磕了一個小時要進步很大了，加油。