首页  /  数据结构教程  /  堆排序  /  

堆排序

点击打开在线编译器,边学边练

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;
}


上一课:希尔排序 下一课:归并排序
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记