这个排序算法有点难！——堆排序C++版

一、什么是堆排序？

1、什么是堆

堆是一种特殊的二叉树，它具有以下两个性质：1）每个节点的值大于等于其每个子节点的值。2）它是完全平衡的二叉树，最后一层的叶子节点都在最左侧。

堆分为最大堆和最小堆，最大堆的值不能小于其左右孩子的值，最小堆的值不能大于其左右孩子。

2、堆排序

堆排序是利用堆这种数据结构设计排序算法，它是一种选择排序，这种排序算法有构建初始堆和交换重建堆两部分组成。可以构建最大堆或者最小堆来进行升序或者降序排列数据。

3、堆排序步骤

以最大堆排序为例，数据用数组的存的话，第一步循环遍历所有的元素，先构建一个根元素的最大的堆，这个最大根数据在0号位置；第二步在最大堆的基础上开始进行排序，从后向前循环遍历所有的元素，每一次遍历都把最大的元素放到当次的最大位置上，直到排序完成。（看下面的代码注释）

二、堆排序的优缺点

优点：
1）效率高，时间复杂度为O(nlogn).
2）需要的辅助空间少，辅助空间为O(1)，节省内存。
3）堆排序相对稳定。
缺点：
2）构建过程复杂，需要构建初始堆和交换重建堆两部分，维护起来比较麻烦。

三、代码示例

// HeapSort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>
void moveDownMax(T data[], int first, int last)
{
    int largest = 2 * first + 1; //当前元素的位置
    while (largest<=last) // 当前元素在数组的范围内
    {
        if (largest<last && data[largest]<data[largest+1]) // 左右子节点进行比较，如果左边的小于右边则继续比较，找到最大的子节点
        {
            largest++;
        }
        if (data[first] < data[largest]) // 如果父节点小于子节点继续进行调整
        {
            swap(data[first], data[largest]); // 父节点和子节点交换
            first = largest; // 把最大的元素赋值给根节点
            largest = 2 * first + 1;
        }
        else 
        {
            largest = last + 1;  // 当父节点大于子节点时调整完毕 跳出循环
        }
    }
}

template<typename T>
void heapSortMax(T data[], int size) // 最大堆排序
{
    for (int i = size / 2 - 1; i >= 0; --i) // 创建堆
    {
        moveDownMax(data, i, size - 1);
    }
    cout << "------构建初始化后的最大堆------" << endl;
    for (int i = 0; i < size; ++i)
    {
        cout << data[i] << "->";
    }
    cout << endl;
    for (int i = size - 1; i >= 1; --i)
    {
        swap(data[0], data[i]); // 将最大的元素放到位置i上
        moveDownMax(data, 0, i - 1); // 重新构建堆
    }
}

template<typename T>
void moveDownMin(T data[], int first, int last)
{
    int least = 2 * first + 1;
    while (least <= last)
    {
        if (least<last && data[least]>data[least+1])// 左右子节点进行比较，如果左边的大于右边则继续比较，找到最小的子节点
        {
            least++;
        }
        if (data[first]>data[least])// 如果父节点大于子节点继续进行调整
        {
            swap(data[first], data[least]); // 父节点和子节点交换
            first = least;// 把最小的元素赋值给根节点
            least = 2 * first + 1;
        }
        else
        {
            least = last + 1;// 当父节点小于子节点时调整完毕 跳出循环
        }
    }
}

template<typename T>
void heapSortMin(T data[], int size)// 最小堆排序
{
    for (int i = size / 2 - 1; i >= 0; --i) // 创建堆
    {
        moveDownMin(data, i, size - 1);
    }
    cout << "------构建初始化后的最小堆------" << endl;
    for (int i=0; i<size; ++i)
    {
        cout << data[i] << "->";
    }
    cout << endl;
    for (int i = size - 1; i >= 1; --i)
    {
        swap(data[0], data[i]); // 将最小的元素放到位置i上
        moveDownMin(data, 0, i - 1); // 重新构建堆
    }
}


int main()
{
    cout << "---------堆排序---------" << endl;
    int tempArr[] = { 0,4,3,5,6,7,9,8,2,1,10,13,14,16,15,12,17,19,18,20 };
    int arrSize = sizeof(tempArr) / sizeof(tempArr[0]);
    cout << "arrSize=" << arrSize << endl;
    cout << "---------排序前---------" << endl;
    for (auto iter : tempArr)
    {
        cout << iter << "  ";
    }
    cout << endl;

    heapSortMax(tempArr, arrSize); // 最大堆排序
    cout << "---------最大堆排序后---------" << endl;
    for (auto iter : tempArr)
    {
        cout << iter << "  ";
    }
    cout << endl;


    heapSortMin(tempArr, arrSize);// 最小堆排序
    cout << "---------最小堆排序后---------" << endl;
    for (auto iter : tempArr)
    {
        cout << iter << "  ";
    }
    cout << endl;
    std::cout << "Hello World!n";
    getchar();
}

运行结果：

能力有限，如有错误，多多指教！原创不易，点赞鼓励一下吧！