堆排序

堆

堆必须同时具备两个特性：1）结构性；2）堆序性

结构性：

堆是一棵完全二叉树，所谓完全二叉树即叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

堆序性：

堆序性说得通俗一点儿就是，父节点中的元素不小于（不大于）任意子节点的元素。
所以，在一个大根堆中，一个节点的元素在其子树所有元素组成的集合中必定是最大值。

堆的存储

一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。

节点下沉

“节点下沉”的目的是在此二叉树中将根节点的元素放至合适的坑位，相应地调整其他元素，最终使得包括根节点在内的整棵二叉树都满足“堆序性”。

“节点下沉”的实施方案说来也很简单：当父节点的元素值小于左子节点的元素值或者右子节点的元素值时，将父节点的元素值与左右子节点较大的元素值进行交换，针对交换后的父节点，循环执行“元素下沉”操作，“元素下沉”的终止条件就是父节点的元素值不小于其任意左右子节点的元素值，或者当前父节点无子节点（即当前节点为叶子节点）。

算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

#include <stdio.h>
#define LeftChild(i) (2*(i)+1)
void swap(int *a,int *b){
    int c = *a;
    *a = *b;
    *b = c;
}

//下沉
void downSortArray(int num[], int index,int count){
    int i = index;
    int child;
    for (;LeftChild(i)<count; i = child){
        //取子节点中 较大节点
        child = LeftChild(i);
        if ((child +1)< count && num[child+1]>num[child]){
            child++;
        }
        
        //如果需要则交换
        if (num[i]<num[child]){
            swap(&num[i],&num[child]);
        }else{
            break;
        }
    }
}

//堆排序
void heapSort(int num[], int count){
    //构建大根堆
    for (int i = count/2; i>=0; i--) {
        downSortArray(num,i,count);
    }
    for (int i=0; i<count; i++) {
        printf("%d ",num[i]);
    }
    printf("\n");
    //并交换，下沉
    for (int i = count-1; i>=0; i--) {
        swap(&num[i],&num[0]);
        downSortArray(num,0,i);
    }
}

int main() {
    //读取输入数据
    int num[100] = {0};
    int count;
    scanf("%d",&count);
    for (int i = 0; i<count; i++) {
        scanf("%d",&num[i]);
    }
    
    //堆排序
    heapSort(num,count);
    
    //输出结果
    for (int i=0; i<count; i++) {
        printf("%d ",num[i]);
    }
    printf("\n");
}

复杂度分析

堆排序是一种选择排序，其时间复杂度为O(nlogn)

参考

浅谈堆排序

如何进行堆排序