排序——堆排序（Heap Sortd）-蒲公英云

排序——堆排序（Heap Sortd）

堆排序：是指利用堆这种数据结构所设计的排序算法，可以利用数组的特点快速定位指定索引的元素，堆分为大根堆和小根堆，是完全二叉树。

大根堆：每个节点上的值都不大于它父节点的值

小根堆：每个节点上的值都不小于它父节点的值

完全二叉树：除最后一层外每一层上的节点数都达到最大值，在最后一层上只缺少最右边若干个节点。

实例：

#include "stdafx.h"
#include <iostream>
using namespace std;
//堆调整
template<class T>
void HeapAdjust(T data[], int i, int arrsize)
{
    if (i > arrsize / 2)    //i为叶子节点
        return;
    int lchiled = i * 2;        //左叶子节点
    int rchiled = i * 2 + 1;    //右叶子节点
    int max = i;
    if (lchiled <= arrsize && data[lchiled] > data[max])
    {
        max = lchiled;
    }
    if (rchiled <= arrsize && data[rchiled] > data[max])
    {
        max = rchiled;
    }
    if (max != i)
    {
        swap(data[i], data[max]);
        HeapAdjust(data, max, arrsize);
    }
}
//创建堆
template<class T>
void BuiledHeap(T data[], int arrsize)
{
    for (int i = arrsize / 2; i >= 1; i--)
    {
        HeapAdjust(data, i, arrsize);
    }
}
//堆排序
template<class T>
void HeapSort(T data[], int arrsiz)
{
    if (arrsiz < 2)
        return;
    BuiledHeap(data, arrsiz);
    swap(data[1], data[arrsiz]);
    for (int i = arrsiz - 1; i > 1; i--)
    {
        HeapAdjust(data, 1, i);
        swap(data[1], data[i]);
    }
}
template<class T>
void Sprint(T data[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << data[i + 1] << " ";
    }
    cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = { 0, 3, 5, 1, 4, 6, 2 };
    int n = sizeof(data) / sizeof(int) -1;    //数组从1开始
    HeapSort(data, n);
    Sprint(data, n);
    return 0;
}