Heapsort

一，概念

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；

小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間複雜度為 Ο(nlogn)。

二，算法思想：

堆排序的基本思想是：1、将帶排序的序列構造成一個大頂堆，根據大頂堆的性質，目前堆的根節點（堆頂）就是序列中最大的元素；2、将堆頂元素和最後一個元素交換，然後将剩下的節點重新構造成一個大頂堆；3、重複步驟2，如此反複，從第一次建構大頂堆開始，每一次建構，我們都能獲得一個序列的最大值，然後把它放到大頂堆的尾部。最後，就得到一個有序的序列了

三，代碼：

#include<stdio.h>
#include<stdlib.h>
//堆排序用于查找最大值 或者 最小值
void show(int *p, int n)
{
    for (int i = 0; i < n;i++)
    {
        printf("%4d", p[i]);
    }
    printf("\n");
}
void findmax(int *arr, int size)
{
    for (int j = size - 1; j>0; j--)//從尾部循環到頭部
    {
        int parent = j / 2;//定義
        int child = j;//記錄目前下标
        if (j < size - 1 && arr[j]< arr[j + 1])//該行的j<size-1 可以避免數組越界
        {
                child++;
        }
        if (arr[child]>arr[parent])
        {
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
        }
    }
}
void heapsort(int *arr, int size)
{
    for (int j = size; j > 0; j--)
    {
        findmax(arr, j);
        int temp = arr[0];
        arr[0] = arr[j - 1];
        arr[j - 1] = temp;
    }
}
void heapsort1(int *arr, int size)
{
    
    for (int i = 0; i < size; i++)
    {
        findmax(arr + i, size-i);
    }
}
void main()
{

    int a[11] = { 10, 13, 99, 12, 30, 14, 50, 19, 60, 29 };
    int b[6] = { 2, 5, 66, 25, 8, 99 };
    //printf("%d\n", a[10]);
    //int *pp = a;
    //printf("%d", pp[10]);
    //show(b, 6);
    //findmax(a, 11);
    //show(a, 11);
    //heapsort(a, 11);
    heapsort1(a, 10);
    show(a, 11);

}


void findmax1(int *arr1, int size1)
{
    int *arr = arr1;
    int size = size1;
    for (int i = 0; i < size1; i++)
    {
        arr = arr1;
        arr = arr + i; 
        size = size1 - i;
        for (int j = size-1; j > 0; j--)//從尾部循環到頭部
        {
            int parent = j / 2;//定義
            int child = j;//記錄目前下标
            if (j < size - 1 && arr[j]< arr[j + 1])//該行的j<size-1 可以避免數組越界
            {
                child++;
            }
            if (arr[child]>arr[parent])//最大值攀頂
            {
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
            }
        }
    }
}