來源：guguoyu.blog.csdn.net/article/details/81283998

• 一 準備知識
• 1.1 大根堆和小根堆
• 二 堆排序基本步驟
• 2.1 構(gòu)造堆
• 2.2 固定最大值再構(gòu)造堆
• 三 總結(jié)
  四 代碼

一 準備知識

堆的結(jié)構(gòu)可以分為大根堆和小根堆，是一個完全二叉樹，而堆排序是根據(jù)堆的這種數(shù)據(jù)結(jié)構(gòu)設計的一種排序，下面先來看看什么是大根堆和小根堆

1.1 大根堆和小根堆

性質(zhì)：每個結(jié)點的值都大于其左孩子和右孩子結(jié)點的值，稱之為大根堆；每個結(jié)點的值都小于其左孩子和右孩子結(jié)點的值，稱之為小根堆。如下圖

我們對上面的圖中每個數(shù)都進行了標記，上面的結(jié)構(gòu)映射成數(shù)組就變成了下面這個樣子

還有一個基本概念：查找數(shù)組中某個數(shù)的父結(jié)點和左右孩子結(jié)點，比如已知索引為**i** 的數(shù)，那么

1.父結(jié)點索引：(i-1)/2（這里計算機中的除以2，省略掉小數(shù)）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

所以上面兩個數(shù)組可以腦補成堆結(jié)構(gòu)，因為他們滿足堆的定義性質(zhì)：

大根堆： arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆： arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

二 堆排序基本步驟

基本思想：

1.首先將待排序的數(shù)組構(gòu)造成一個大根堆，此時，整個數(shù)組的最大值就是堆結(jié)構(gòu)的頂端

2.將頂端的數(shù)與末尾的數(shù)交換，此時，末尾的數(shù)為最大值，剩余待排序數(shù)組個數(shù)為n-1

3.將剩余的n-1個數(shù)再構(gòu)造成大根堆，再將頂端數(shù)與n-1位置的數(shù)交換，如此反復執(zhí)行，便能得到有序數(shù)組

2.1 構(gòu)造堆

將無序數(shù)組構(gòu)造成一個大根堆（升序用大根堆，降序就用小根堆）

假設存在以下數(shù)組

主要思路：第一次保證0~0位置大根堆結(jié)構(gòu)（廢話），第二次保證0~1位置大根堆結(jié)構(gòu)，第三次保證0~2位置大根堆結(jié)構(gòu)...直到保證0~n-1位置大根堆結(jié)構(gòu)（每次新插入的數(shù)據(jù)都與其父結(jié)點進行比較，如果插入的數(shù)比父結(jié)點大，則與父結(jié)點交換，否則一直向上交換，直到小于等于父結(jié)點，或者來到了頂端）

插入6的時候，6大于他的父結(jié)點3，即arr(1)>arr(0)，則交換；此時，保證了0~1位置是大根堆結(jié)構(gòu)，如下圖：

(友情提示：待交換的數(shù)為藍色，交換后的數(shù)為綠色)

插入8的時候，8大于其父結(jié)點6，即arr(2)>arr(0),則交換；此時，保證了0~2位置是大根堆結(jié)構(gòu)，如下圖

插入5的時候，5大于其父結(jié)點3，則交換，交換之后，5又發(fā)現(xiàn)比8小，所以不交換；此時，保證了0~3位置大根堆結(jié)構(gòu)，如下圖

插入7的時候，7大于其父結(jié)點5，則交換，交換之后，7又發(fā)現(xiàn)比8小，所以不交換；此時整個數(shù)組已經(jīng)是大根堆結(jié)構(gòu)

2.2 固定最大值再構(gòu)造堆

此時，我們已經(jīng)得到一個大根堆，下面將頂端的數(shù)與最后一位數(shù)交換，然后將剩余的數(shù)再構(gòu)造成一個大根堆

（友情提示：黑色的為固定好的數(shù)字，不再參與排序）

此時最大數(shù)8已經(jīng)來到末尾，則固定不動，后面只需要對頂端的數(shù)據(jù)進行操作即可，拿頂端的數(shù)與其左右孩子較大的數(shù)進行比較，如果頂端的數(shù)大于其左右孩子較大的數(shù)，則停止，如果頂端的數(shù)小于其左右孩子較大的數(shù)，則交換，然后繼續(xù)與下面的孩子進行比較

下圖中，5的左右孩子中，左孩子7比右孩子6大，則5與7進行比較，發(fā)現(xiàn)5<7，則交換；交換后，發(fā)現(xiàn)5已經(jīng)大于他的左孩子，說明剩余的數(shù)已經(jīng)構(gòu)成大根堆，后面就是重復固定最大值，然后構(gòu)造大根堆

如下圖：頂端數(shù)7與末尾數(shù)3進行交換，固定好7，

剩余的數(shù)開始構(gòu)造大根堆 ，然后頂端數(shù)與末尾數(shù)交換，固定最大值再構(gòu)造大根堆，重復執(zhí)行上面的操作，最終會得到有序數(shù)組

三 總結(jié)

到這里，大家應該對堆排序都有了自己的見解，我們對上面的流程總結(jié)下：

1、首先將無需數(shù)組構(gòu)造成一個大根堆（新插入的數(shù)據(jù)與其父結(jié)點比較）

2、固定一個最大值，將剩余的數(shù)重新構(gòu)造成一個大根堆，重復這樣的過程

四 代碼

代碼中主要兩個方法：

1、將待排序數(shù)組構(gòu)造成一個大根堆（元素上升）

2、固定一個最大值，將剩余的數(shù)再構(gòu)造成一個大根堆（元素下降）

    //堆排序
    public static void heapSort(int[] arr) {
        //構(gòu)造大根堆
        heapInsert(arr);
        int size = arr.length;
        while (size > 1) {
            //固定最大值
            swap(arr, 0, size - 1);
            size--;
            //構(gòu)造大根堆
            heapify(arr, 0, size);

        }

    }

    //構(gòu)造大根堆（通過新插入的數(shù)上升）
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //當前插入的索引
            int currentIndex = i;
            //父結(jié)點索引
            int fatherIndex = (currentIndex - 1) / 2;
            //如果當前插入的值大于其父結(jié)點的值,則交換值，并且將索引指向父結(jié)點
            //然后繼續(xù)和上面的父結(jié)點值比較，直到不大于父結(jié)點，則退出循環(huán)
            while (arr[currentIndex] > arr[fatherIndex]) {
                //交換當前結(jié)點與父結(jié)點的值
                swap(arr, currentIndex, fatherIndex);
                //將當前索引指向父索引
                currentIndex = fatherIndex;
                //重新計算當前索引的父索引
                fatherIndex = (currentIndex - 1) / 2;
            }
        }
    }
    //將剩余的數(shù)構(gòu)造成大根堆（通過頂端的數(shù)下降）
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while (left < size) {
            int largestIndex;
            //判斷孩子中較大的值的索引（要確保右孩子在size范圍之內(nèi)）
            if (arr[left] < arr[right] && right < size) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            //比較父結(jié)點的值與孩子中較大的值，并確定最大值的索引
            if (arr[index] > arr[largestIndex]) {
                largestIndex = index;
            }
            //如果父結(jié)點索引是最大值的索引，那已經(jīng)是大根堆了，則退出循環(huán)
            if (index == largestIndex) {
                break;
            }
            //父結(jié)點不是最大值，與孩子中較大的值交換
            swap(arr, largestIndex, index);
            //將索引指向孩子中較大的值的索引
            index = largestIndex;
            //重新計算交換之后的孩子的索引
            left = 2 * index + 1;
            right = 2 * index + 2;
        }

    }
    //交換數(shù)組中兩個元素的值
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

友情提示：手機觀看，可以左右滑動

若覺得文章對你有幫助，隨手轉(zhuǎn)發(fā)分享，也是我們繼續(xù)更新的動力。