堆排序（HeapSort）

http://blog.csdn.net/magicharvey/article/details/10207931

算法描述

堆排序（HeapSort）不是一个稳定的排序。它是使用完全二叉树的数据结构进行排序的算法。

基本思想

若在输出堆顶得最小值之后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n哥元素中的次小值，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

实现步骤

1. 将原始序列调整为最小或者最大堆序列，从而建立初始堆；
2. 将堆顶元素与序列的最后一个元素进行交换；
3. 去掉最后一个元素，将剩下的序列重新调整成为一个最小或者最大堆序列;
4. 重复2和3，直到堆中只有一个元素为止。

算法实现

代码在xcode中验证，可以直接使用

//调整堆函数
void H_Sort(int a[], int index, int length)
{
    int left_index = index*2 +1;
    int right_index = index*2 +2;
    int min_index = index;
    //判断左子节点与父节点的大小
    if( left_index <= length && a[index] > a[left_index])
    {
        min_index = left_index;
    }
    //判断右子结点与最小节点的大小
    if( right_index <= length && a[min_index] > a[right_index])
    {
        min_index = right_index;
    }
    
    //如果最小的节点不是父节点，则进行调整
    if (min_index != index)
    {
        int temp = a[index];
        a[index] = a[min_index];
        a[min_index] = temp;
        
        H_Sort(a, min_index, length);
    }
}


//建立初始堆，并完成堆的筛选过程
void HeapSort(int a[], int length)
{
    int num = length-1;   //保存堆的最后一个元素的下标
    
    //调整数组为一个最小堆
    //第一个元素为length/2-1，而不是(length-1)/2
    for (int index = length/2-1; index >= 0; index--) {
        H_Sort(a, index, length-1);
    }
    
    //交换堆的最顶端元素与最小堆的最右端元素，将长度减一，重新调整堆
    //当num=0时，不能在进行--
    while(num>0)
    {
        int temp = a[0];
        a[0] = a[num];
        a[num] = temp;
        
        num--;
        H_Sort(a, 0, num);
    }
}

性能分析

堆排序的时间开销主要由建立初始堆和调整堆的时间开销所组成。其中建立初始堆的时间复杂度为o(n*logn)，调整堆的时间复杂度为o(n*lgn)，所以总的时间复杂度为o(n*logn)。

堆排序的最好和最坏时间复杂度都是o(n*logn),空间复杂度为o(1)。

堆排序不适合有序数组的排序。