堆排序，堆排序復雜度

堆排序，堆排序復雜度

堆排序是基於二叉樹。n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：

(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），當然，這是小根堆，大根堆則換成>=號。//k(i）相當於二叉樹的非葉子結點，K(2i）則是左子節點，k(2i+1）是右子節點。

堆排序的幾個關鍵點：

1、一個節點的兩個子節點已經是有序堆，調整這個節點為有序堆(遞歸調整)；

2、創建堆：調整第一個非葉節點為有序堆，逐級向上，直到整個數組為有序堆。

3、堆頂與最後一個葉子節點調換，堆變小，再調整堆，再調換，直到堆大小為1，排序完成。

附上代碼：

#include "stdafx.h"
#include <stdio.h>

/*
 * L     初始無序堆
 * n     節點序號
 * size  無序堆節點個數
 */
void Heapify(int L[], int n, int size)
{
    int rchild=2*n+1;
    int lchild=2*n;
    if (rchild<=size)
    {
        int max=L[lchild]>L[rchild] ? lchild : rchild;
        if (L[n]<L[max])
        {
            int temp=L[n];
            L[n]=L[max];
            L[max]=temp;
            Heapify(L,max,size);
        }
    }
    else if (lchild==size)
    {
        if (L[n]<L[lchild])
        {
            int temp=L[n];
            L[n]=L[lchild];
            L[lchild]=temp;
        }
    }
}

// 建堆（大根堆）
void BuildHeap(int L[], int size)
{
    for (int i=size/2; i>0; i--) // 從最低層的節點開始創建有序堆，直到整個堆是有序堆。
    {
        Heapify(L,i,size);
    }
}

// L[0]是暫存區
void HeapSort(int L[], int size)
{
    BuildHeap(L,size);
    for (int i=size; i>0; i--)
    {
        L[0]=L[1];
        L[1]=L[i];
        L[i]=L[0];
        Heapify(L,1,i-1);
    }
}

int main(int argc, char* argv[])
{
    // 待排序數據不包括L[0]
    int L[13]={5,1,7,2,90,6,-5,23,10,4,50,12,5};
    int i=0;
    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    HeapSort(L,12);

    for (i=1; i<13; i++)
    {
        printf("%5d",L[i]);
    }
    printf("\n");

    return 0;
}