堆排序

[bosthhe1]

要想使用堆排序，首先要满足堆是一个完全二叉树，然后需要满足根节点的下一层为堆排序，满足后再对堆进行排序，堆的时间复杂度为O(N); 堆排序分为大堆和小堆： 排列大堆时根节点的子节点都小于根节点，及第一个根节点最大，大于所有子节点 排列小堆时根节点的子节点都大于根节点，及第一个根节点最小，小于所有子节点 再堆排序之前，需要先设置一个堆，如果从小到大排序中，需要堆是大堆，如果需要从大到小排列，需要是小堆。 需要注意的是，堆排序始终是从根节点向下排序，至于根节点是哪个节点就具体分析，排序一次无法保证为大堆或者小堆，所以要进行多次排序

[bosthhe1]

void Swap(int *arr, int *ar)
{
    int tmp = *arr;
    *arr = *ar;
    *ar = tmp;
}
//建立大堆
void AdjeadHeap(int *arr, int size,int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child<=size)
    {
        if (child + 1 <= size)
        {
            if (arr[child] > arr[child + 1])
            {
                child = child;
            }
            else
            {
                child++;
            }
        }
        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int *arr, int size)
{
//开始建立大堆
    int end = (size - 1) / 2;
//从底层开始编译，保证根节点的左右为有序
    for (int i = end; i >= 0; i--)
    {
        AdjeadHeap(arr, size, i);
    }
    end = size;
//开始排序
    while (end > 0)
    {//先把最大的和最小的交换，然后最大的到了最后一个子节点，最小的到了根节点，然后将end--（就相当于把最后一个剔除）；然后进行排序，因为上面已经初始化有序了；所有第二次排序很快。
        Swap(&arr[0], &arr[end]);
        end--;
        AdjeadHeap(arr, end, 0);
    }
}

void TestHeap1()
{
    int arr[10] = { 1, 4, 5, 6, 7, 8, 9, 3, 2, 10 };
    int size = sizeof(arr) / sizeof(arr[0])-1;
    HeapSort(arr, size);
    for (int i = 0; i <= size; i++)
    {
        printf("%d ", arr[i]);
    }
}
int main()
{
    TestHeap1();
    system("pause");
    return 0;
}