基本思想:①把一个数组A构造成一个二叉最大堆,②然后交换下标为0和下标为A-1的值,且每次heap_size - - ,③然后再调整该堆为最大堆。最后循环执行②③,直至heap_size有效元素为1,堆排序算法结束。

为了更加清楚的了解堆排序的整个过程,我们先来介绍一下最大堆:

二叉堆可以分为两种形式:最大堆和最小堆。在这两种堆中,结点的值都要满足堆的性质,但一些细节定义则有所差异。在最大堆中,最大堆性质是指除了根以外的所有结点i都要满足:

A[ PARENT( i ) ] >= A[ i ]

也就是说,某个结点的值至多与其父节点一样大。因此,堆中的最大元素存放在根节点中;并且,在任一子树中,该子树所包含的所有结点的值都不大于该子树根节点的值。

最小堆的组织方式正好相反:最小堆性质是指除了跟以外的所有结点i都有:

A[ PARENT( i ) ] <= A( i )

最小堆中的最小元素存放在根节点中。

在堆排序中,我们使用的是正是最大堆。最小堆通常用于构造优先队列。

如下图所示:右边是一个数组A,左边就是由数组A构成的最大堆。如果树的根节点是A[1],那么给定一个下标i,我们很容易计算得到它的父节点,左孩子和右孩子的下标:

PARENT( i ):

return i/2

LEFT( i ):

return 2i

RIGHT( i ):

return 2i+1


----------

排序算法:堆排序
时间:2018年1月13日
时间复杂度:O(nlogn)
空间复杂度:O(1)
稳  定  性:不稳定
by Ingran

----------

#include <iostream>
#include <iomanip>
#include <time.h>

void Swap(int a[], int i, int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void MAX_HEAPIFY(int a[],int heap_size, int i)//调整最大堆
{
    int l = 2 * i;
    int r = 2 * i + 1;
    int largest = 0;//保存(父节点,左子树,右子树)中的最大值

    if (l <= heap_size && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if (r <= heap_size && a[r] > a[largest])
        largest = r;

    if (largest != i)
    {
        Swap(a, i, largest);//交换a[i]与a[largeset]
        MAX_HEAPIFY(a,heap_size,largest);
    }
}

void BUILD_MAX_HEAP(int a[],int len)//构建最大堆
{
    int heap_size = len;

    for (int i = len / 2; i >= 0; i--)
    {
        MAX_HEAPIFY(a, heap_size, i);
    }
}

void HEAP_SORT(int a[], int len)//堆排序
{
    int heap_size = len;
    BUILD_MAX_HEAP(a, len);

    for (int i = len; i >= 1; i--)
    {
        Swap(a, i, 0);
        heap_size = heap_size - 1;
        MAX_HEAPIFY(a, heap_size, 0);
    }
}

int main()
{
    int n = 0;
    int *p = nullptr;
    srand((unsigned)time(NULL));

    std::cout << "请输入随机数个数:" << std::endl;
    std::cin >> n;
    p = new int[n];

    std::cout << "排序前:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        p[i] = rand() % 21;
        std::cout << p[i] << "  ";
        if (i % 10 == 9 && i != 0)
            std::cout << std::endl;
    }

    HEAP_SORT(p, n-1);

    std::cout << std::endl << "排序后:" << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << std::setw(2)<< p[i] << "  ";
        if (i % 10 == 9)
            std::cout << std::endl;
    }

    system("pause");
    return 0;
}