排序算法之堆排序

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1、算法描述

1. 将初始待排序关键字序列(R1,R2….Rn)构建成最大堆，此堆为初始的无序区；

2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

2、算法图解

（1）最大堆与最小堆

（2）构建最大堆

（3）堆排序

3、算法demo

#include <bits/stdc++.h>
using namespace std;

//建立堆积树（从下往上调整）
void create_heap(vector<int> &a, int i, int heapsize)
{
    int largest = i;
    int temp = a[i];
    int left = 2 * i + 1;
    int right = left + 1;
    //判断当前节点和左右儿子的关系，并用largest记录值较大的结点编号
    if (left < heapsize && a[i] < a[left])
        largest = left;
    if(right < heapsize && a[largest] < a[right])
        largest = right;
    if(largest != i)
    {
        swap(a[i], a[largest]);//如果有儿子节点大于父节点则交换
        //避免交换后，largest这个节点和其儿子节点的结构发生混乱，不满足最大堆，所以递归调整
        create_heap(a, largest, heapsize);
    }
}

//堆排序
void heap_sort(vector<int> &a)
{
    int length = a.size();
    // 从最后一个非叶子节点向上建立最大堆
    for(int i = length/2 - 1; i >= 0; --i)
    {
        create_heap(a, i, length);
    }
    // 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，
    // 再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
    for(int i = length - 1; i >= 0; --i)
    {
        swap(a[i], a[0]);
        create_heap(a, 0, i);
    }
}

int main(int argc, char const *argv[])
{
    vector<int> vec1 = {7, 8, 9, 5, 3, 6, 1};
    heap_sort(vec1);
    for (const auto v : vec1)
        cout << v << " ";
    cout << endl;

    vector<int> vec2 = vec1;
    //STL中的建堆和堆排序
    make_heap(vec2.begin(), vec2.end());
    sort_heap(vec2.begin(), vec2.end());
    for (const auto v : vec2)
        cout << v << " ";
    cout << endl;
    system("pause");
    return 0;
}

4、算法总结

  堆排序是一种不稳定排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)。

  简单总结下堆排序的基本思路：

1. 将无需序列构建成一个堆，根据升序降序需求选择最大堆或最小堆；

2. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端；

3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

参考：https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.cnblogs.com/onepixel/articles/7674659.html