复习数据结构：排序算法（六）—

复习数据结构：排序算法（六）——堆排序

对于堆排序，前面一篇博文中已经复习到了堆排序，这里就简单介绍一下，并给出核心部分的解释。

堆排序是一种不稳定的排序，也是内排序。

时间复杂度为O(nlogn)。

以最大堆为例，堆排序的基本思想是：

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，则整个排序过程完成。

其实，堆排序最重要的两部分就是：初始化堆和调整堆。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std; 
// 调整堆函数
void HeapAdjust(int *a, int i, int size)  // a：数组；i：节点index；size：树的规模
{
    int lchild = 2 * i;   // 节点的左孩子编号
    int rchild = 2 * i + 1;   // 节点的右孩子编号
    int max = i;  //节点编号备份
    if(i <= size/2 - 1)
    {
        if(lchild <= size && a[lchild] > a[max])  // 左孩子比节点值要大
            max = lchild; 
        if(rchild <= size && a[rchild] > a[max])  // 右孩子比节点值要大
            max = rchild; 
        if(max != i)  // 如果上面发生了交换，也就是如果上面有if成立了
        {
            swap(a[i], a[max]);   // 首先要交换二者的真实值，因为上面只是index的交换
            HeapAdjust(a, max, size);  // 其次，需要判断交换之后还需要重新调整吗
        }
    }
}
//建立堆函数
void BuildHeap(int *a, int size)  
{
    int i; 
    for(i = size/2 - 1; i >= 0; i--)  // 非叶子节点最大序号值为size/2，需要遍历所有的节点
    {
        HeapAdjust(a, i, size);   // 调整
    }
}
// 堆排序函数
void HeapSort(int *a, int size)
{
    int i; 
    BuildHeap(a, size); 
    for(i = size; i >= 0; i--)
    {
        swap(a[0], a[i]);  //  交换堆顶和最后一个元素，每次将剩余元素中的最大者放到最后面
        HeapAdjust(a, 0, i-1);  // 重新调整堆顶节点成为大顶堆，这个时候就要除出最后一个元素，范围是1~n-1
    }
}
int main()
{
    int a[] = {100, 16, 20, 3, 11, 17, 8};
    int size = 7; 
    HeapSort(a, size); 
    for(int i = 0; i < size; i++)
    {
        cout<<a[i]<<endl; 
    }
    cout<<endl; 
    return 0; 
}