0%
这是一片思考的空间 -- arthinking
Spring 重构&代码整洁之道 软件设计 JVM 并发编程 数据结构与算法 分布式 存储 网络 微服务 设计模式
Java技术栈 - 涉及Java技术体系

数据结构笔记 - 排序算法 堆排序算法

堆排序:

其基本思想是将待排序的数组构造成一个大顶堆,从而获得数组最大的元素,即当前的根节点。将其移走之后,再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行,最后得到一个有序序列。

堆排序属于选择排序。

堆排序的过程:

  • ① 循环处理元素构造大顶堆
  • ② 获取堆顶元素并和最后一个叶节点交换位置
  • ③ 重新构建大顶堆,元素个数减一(除去最后一个叶节点,即选出的最大值)。
  • ④ 循环第2、3个步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>

#define MAXSIZE 100 /* 待排序数组的大小 */

typedef struct
{
int r[MAXSIZE+1]; /* 待排序数组r,r[0]为哨兵或临时变量 */
int length; /* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 堆排序算法 */
void HeapSort(SortList *L)
{
int i;
/* 把待排序数组L构造成大顶堆 */
for(i=L->length/2;i>0;i--)
HeapAdjust(L,i,L->length);

for(i=L->length;i>1;i--)
{
/* 将当前大顶堆的根节点即数组最大值和未排序钱的数组最后一个元素交换位置 */
int temp=L->r[1];
L->r[1]=L->r[i];
L->r[i]=temp;
/* 把待排序数组L(1 to i-1)中剩余的元素继续构造成大顶堆 */
HeapAdjust(L,1,i-1);
}
}

/* 已知r[s...m]中除了r[s]元素之外均满足堆的定义,本函数通过调整r[s]元素,使待排序数组L构造成大顶堆 */
void HeapAdjust(SortList *L,int s,int m)
{
int temp,j;
temp=L->r[s];
/* 沿着元素比较大的结点往下找 */
for(j=2*s;j<=m;j*=2)
{
/* 比较左子树和右子数的大小,获取较大子数的下标j */
if(j<m && L->r[j]<L->r[j+1])
++j;
/* r[s]已经是最大的,无需改变位置 */
if(temp>=L->r[j])
break;
/* 把较大的子节点赋值给r[s] ,此时r[s]与r[j]相等 */
L->r[s]=L->r[j];
/* 从被替换的子节点j开始继续下一个循环,查找j的子节点 */
s=j;
}
/* 此时的r[s]为循环到最后一个处理的父节点 */
L->r[s]=temp; /* 此时的r[s]为最后一个被交换的子节点,而不是开始的,把temp值赋予该结点,实现和需要处理元素的交换 */
}

堆排序算法复杂度分析:

在初始化构建大顶堆时,每个非终端结点最多比较两次,所有,这个构建的过程时间复杂度为O(n)。

排序过程中,第i次取堆顶记录重建大顶堆的时间复杂度为O(logi),并且需要取n-1次堆顶记录,所有重建堆的时间复杂度为O(nlogn)。总体上来说,堆排序的时间复杂度为:O(nlogn)。

因为初始化构建堆所需比较次数较多,所以堆排序不适合待排序元素较少的情况。

欢迎关注我的其它发布渠道

订阅IT宅
内功修炼
Java技术栈
Java架构杂谈是IT宅精品文章公众号,欢迎订阅:
📄 网络基础知识:两万字长文50+张趣图带你领悟网络编程的内功心法 📄 HTTP发展史:三万长文50+趣图带你领悟web编程的内功心法 📄 HTTP/1.1:可扩展,可靠性,请求应答,无状态,明文传输 📄 HTTP/1.1报文详解:Method,URI,URL,消息头,消息体,状态行 📄 HTTP常用请求头大揭秘 📄 HTTPS:网络安全攻坚战 📄 HTTP/2:网络安全传输的快车道 📄 HTTP/3:让传输效率再一次起飞 📄 高性能网络编程:图解Socket核心内幕以及五大IO模型 📄 高性能网络编程:三分钟短文快速了解信号驱动式IO 📄 高性能网络编程:彻底弄懂IO复用 - IO处理杀手锏,带您深入了解select,poll,epoll 📄 高性能网络编程:异步IO:新时代的IO处理利器 📄 高性能网络编程:网络编程范式 - 高性能服务器就这么回事 📄 高性能网络编程:性能追击 - 万字长文30+图揭秘8大主流服务器程序线程模型
📄 Java内存模型:如果有人给你撕逼Java内存模型,就把这些问题甩给他 📄 一文带你彻底理解同步和锁的本质(干货) 📄 AQS与并发包中锁的通用实现 📄 ReentrantLock介绍与使用 📄 ReentrantReadWriteLock介绍与使用 📄 ReentrantLock的Condition原理解析 📄 如何优雅的中断线程 📄 如何优雅的挂起线程 📄 图解几个好玩的并发辅助工具类 📄 图解BlockingQueue阻塞队列
📄 消息队列那么多,为什么建议深入了解下RabbitMQ? 📄 高并发异步解耦利器:RocketMQ究竟强在哪里? 📄 Kafka必知必会18问:30+图带您看透Kafka
📄 洞悉MySQL底层架构:游走在缓冲与磁盘之间 📄 SQL运行内幕:从执行原理看调优的本质 📄 洞悉Redis技术内幕:缓存,数据结构,并发,集群与算法