堆排序

堆排序

---

堆排序：是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

---

---

---

是否稳定：不稳定
时间复杂度：O(N*lgN)
空间复杂度：O(1)
适用场景：

---

#include <stdio.h>

void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void AdjustHeap(int* array, int size, int parent)
{
    int left = 2 * parent + 1;
    int right = 2 * parent + 2;
    int maxChild;

    if (left >= size)//出口
        return;
    //满足堆要求
    //找最大孩子
    if (right < size) //
    {
        if (array[left] < array[right])
        {
            maxChild = right;
        }
        else
        {
            maxChild = left;
        }
    }
    else
    {
        maxChild = left; //右孩子不存在
    }
    if (array[parent] >= array[maxChild])
    {
        return;
    }
    Swap(&array[parent],&array[maxChild]);

    AdjustHeap(array, size, maxChild);//递归
}

void AdjustHeap_while(int* array, int size, int parent)
{
    int child = 2 * parent + 1;
    while (child < size)//满足堆条件
    {
        if (child + 1 < size&&array[child] < array[child + 1])//找最大元素
        {
            child += 1;//右孩子大
        }
        if (array[child]>array[parent])//判断父节点是否大于孩子(大堆条件)
        {
            Swap(&array[child], &array[parent]);
            parent = child;//向下调整
            child = 2 * parent + 1;
        }
        else
            return;
    }
}

void HeapSort(int* array,int size)
{
    //1.建堆
    int root = ((size - 2)>>1);

    for (; root >= 0; --root)
    {
        AdjustHeap(array,size,root);
        //AdjustHeap_while(array, size, root);
    }
    //2.排序——堆删除
    int end = size - 1;

    while (end > 0)//例：有10个元素，取掉9个大的，剩余那个自然是最小的
    {
        Swap(&array[0], &array[end]);
        AdjustHeap(array, end, 0);
        //AdjustHeap_while(array, end, 0);
        end--;
    }
} 

---

快速排序：https://blog.csdn.net/romantic_c/article/details/79902858
归并排序：https://blog.csdn.net/romantic_c/article/details/79895622
冒泡排序：https://blog.csdn.net/romantic_c/article/details/78278861
计数排序：https://blog.csdn.net/romantic_c/article/details/79898442
选择排序：https://blog.csdn.net/Romantic_C/article/details/81252784
插入排序：https://blog.csdn.net/Romantic_C/article/details/81259718
希尔排序：https://blog.csdn.net/Romantic_C/article/details/81260506