堆排序算法实例详解-数据结构与算法教程

1.复杂度与稳定性

算法时间复杂度

最坏情况：O(n^2)

最好情况：O(n)

平均情况：O(nlogn)

稳定性：不稳定排序

2. 什么是堆？

堆排序是一个比较特殊的排序方式，在学习之前我们必须要了解什么是堆

堆是一种非线性的数据结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组

按照堆的特点可以把堆分为大顶堆和小顶堆

a)大顶堆：每个结点的值都大于或等于其左右孩子结点的值

b)小顶堆：每个结点的值都小于或等于其左右孩子结点的值

这种特性与我们在前面学习查找方法时学过的二叉排序树很相似，这种特殊的数据结构可以让我们快速访问到我们需要的值，如优先队列就使用堆进行处理。

PS:我们这里提到的堆这个概念与编译器概念堆栈需要区分。

3.过程介绍

基本思想：把待排序的元素按照大小在二叉树位置上排列（使用数组模拟，没必要一定使用二叉树），排序好的元素要满足：父节点的元素要大于等于其子节点；这个过程叫做堆化过程，如果根节点存放的是最大的数，则叫做大根堆；如果是最小的数，自然就叫做小根堆了。根据这个特性（大根堆根最大，小根堆根最小），就可以把根节点拿出来，然后再堆化下，再把根节点拿出来，一直循环到最后一个节点，就排序好了。

基本步骤：

其实整个排序主要核心就是堆化过程，堆化过程一般是用父节点和他的孩子节点进行比较，取最大的孩子节点和其进行交换；但是要注意这应该是个逆序的，先排序好子树的顺序，然后再一步步往上，到排序根节点上。然后又相反（因为根节点也可能是很小的）的，从根节点往子树上排序。最后才能把所有元素排序好

4. 相关的代码

请慢慢理解堆排序这一特殊的排序算法，在排序循环中逐步运算出数据。

#include <stdio.h>
 
/* Function: 交换交换根节点和数组末尾元素的值*/
void Swap(int *heap, int len) {
    int temp;
 
    temp = heap[0];
    heap[0] = heap[len-1];
    heap[len-1] = temp;
}
 
/* Function: 构建大顶堆 */
void BuildMaxHeap(int *heap, int len) {
    int i,temp;
    for (i = len/2-1; i >= 0; i--) {
        if ((2*i+1) < len && heap[i] < heap[2*i+1]) {  /* 根节点大于左子树 */
            temp = heap[i];
            heap[i] = heap[2*i+1];
            heap[2*i+1] = temp;
            /* 检查交换后的左子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
        if ((2*i+2) < len && heap[i] < heap[2*i+2]) {  /* 根节点大于右子树 */
            temp = heap[i];
            heap[i] = heap[2*i+2];
            heap[2*i+2] = temp;
            /* 检查交换后的右子树是否满足大顶堆性质 如果不满足 则重新调整子树结构 */
            if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])) {
                BuildMaxHeap(heap, len);
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    int i;
 
    for (i = n; i > 0; i--) {
        BuildMaxHeap(a, i);
        Swap(a, i);
    }
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
 
    return 0;
}