堆排序（选择排序的一种）

https://www.cnblogs.com/MOBIN/p/5374217.html

https://www.cnblogs.com/chengxiao/p/6194356.html

堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它是不稳定排序。

一般升序采用大顶堆，降序采用小顶堆。

//HeapSort堆排序
void Swap(int a[], int i, int j)
{
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void AdjustHeap(int a[], int i, int index)   //调整为大顶堆：升序使用大顶堆，降序使用小顶堆
{
    int left, right, j;
    while ((left = 2*i+1) <= index)
    {
        right = left + 1;
        j = left;
        if (j < index && a[left] < a[right])
        {
            j++;
        }
        if (a[i] < a[j])
        {
            Swap(a, i, j);
            i = j;  //如果进行了交换，需要再重新对该非叶子节点及其儿子进行调整
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int a[], int len)
{
    int index = len -1;
    int i = index / 2 -1;
    for (; i >= 0; i--)
    {
        AdjustHeap(a, i, index);
    }

    while (index > 0)
    {
        Swap(a, 0, index--);
        AdjustHeap(a, 0, index);
    }
}

测试：

int _tmain(int argc, _TCHAR* argv[])
{
    int a[7] = {5,3,7,4,8,1,10};
    //QuickSort2(a, 0, 6);
    //BubbleSort(a, 7);
    HeapSort(a, 7);
    for (int i = 0; i < 7; i++)
    {
        printf("%4d", a[i]);
    }
    return 0;
}

 排序算法总结：https://www.cnblogs.com/RainyBear/p/5258483.html