【算法】堆排序整理

毕业久了，越是基础的东西忘得越彻底，最近也是趁着有时间，赶紧将这些补一补。说到堆排序，是这些排序算法中最后一个重新理解的算法，究其原因，应该是其实现的复杂要高于其他几个算法。

堆排序的结构形态是用一个数组实现了一个二叉树，堆分为最大堆和最小堆两种，最大堆指的是该二叉树的任意一个父节点都比其相连的子节点大，最小堆则反之。对于最大堆来说，其根节点就是整个堆的最大值。

那么对于堆排序算法来说，主要做的是两件事，首先是建堆，之后可以通过堆来依次获取大小有序的数值，每取一个值都需要重新调整堆来保持堆的正确性。

建堆过程稍微复杂一些，以最大堆为例，首先【倒序遍历】含有子节点的节点，【比较】其值与子节点的值，如果子节点的值更大的话，则该节点的值与其子节点的值进行【交换】。交换完成后，需要从子节点的位置继续判断其子节点是否比其大，如果是的话也进行交换，这样依次【向下传递调整】，直到子节点不比父节点大或者已经到达叶子节点为止。

对于关键步骤已经通过【】标注出来了，整个建堆过程有点类似冒泡排序在二叉树上面的实现。完成以上步骤就可以获得一个最大堆。

之后的步骤是获取排序结果，代码在实现的时候比较有意思了，首先取出堆顶的数，让其与数组最后一个数进行交换，之后我们将数组最后一个数从堆里面排除出去，之后从根节点开始，对堆做一次【向下传递调整】操作，那么我们最大值就跑数组最后面去了；第二次，我们再取堆顶的数，让其与数组最后第二个数进行交换，之后我们将数组最后两个数从堆里面排除出去，之后从根节点开始，对堆做一次【向下传递调整】操作。这样一次进行取数、交换、跳转的操作，总共进行N-1次后，我们会发现我们的数组已经以一个从小到大的进行排序了。这就是堆排序的整个过程。

c++代码实现如下

// 最大堆排序 -- 获取从小到大排序的结果

#include <iostream>
using namespace std;

void swep(int i, int j, int *unsortArray) {
    int temp = unsortArray[i];
    unsortArray[i] = unsortArray[j];
    unsortArray[j] = temp;
}

// 调整节点
void adjustCurrent(int index, int* unsortArray, int size) {
    int indexSon1 = index * 2 + 1;
    int indexSon2 = index * 2 + 2;
    bool hasNodeSon1 = (indexSon1 < size); //有第一个子节点
    bool hasNodeSon2 = (indexSon2 < size); //有第二个子节点
    if (!hasNodeSon1)
    {
        //没有子节点不做处理
        return;
    }
    if (unsortArray[index] < unsortArray[indexSon1] 
        || (hasNodeSon2 && unsortArray[index] < unsortArray[indexSon2]))
    {
        int witchSweped = 1;
        if (hasNodeSon2)
        {
            //判断两个子节点中最大的是哪个
            if (unsortArray[indexSon1] > unsortArray[indexSon2])
            {
                swep(indexSon1, index, unsortArray);
            } else {
                swep(indexSon2, index, unsortArray);
                witchSweped = 2;
            }
        }
        else {
            swep(indexSon1, index, unsortArray);
        }
        //向下传递调整
        adjustCurrent(index * 2 + witchSweped, unsortArray, size);

    }
}

void heapSort(int *unsortArray, int size) {
    // 建堆
    for (int i = size/2 - 1; i >= 0; --i)
    {
        //当前节点调整
        adjustCurrent(i, unsortArray, size);
    }

    // 通过堆获取排序结果
    int currentIndex = size - 1;
    while(currentIndex) {
        swep(currentIndex, 0, unsortArray);
        adjustCurrent(0, unsortArray, currentIndex);
        currentIndex --;
    }
}

int main() {
    int unsortArray[] = {9,8,7,6,5,4,3,2,1};
    int size = sizeof(unsortArray)/sizeof(int);
    cout<<"before sort"<<endl;
    for (int i = 0; i < size; ++i)
    {
        cout<<unsortArray[i]<<" ";

    }
    cout<<endl;
    heapSort(unsortArray, size);


    cout<<"after sort"<<endl;
    for (int i = 0; i < size; ++i)
    {
        cout<<unsortArray[i]<<" ";
    }
    cout<<endl;
    return 0;
}