💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:八大排序专栏⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习排序知识
🔝🔝
1. 前言🚩
本期主角:
斯坦福大学计算机教授罗伯特·弗洛伊德
👇👇👇
发明的堆排序
他是在芝加哥大学读的文学系
看他这么艺术的形象
就知道他不是文学派就是抽象派
在学习堆排序之前
我们需要先了解什么是堆
以及堆的C语言实现(详情跳转)堆详解
注:这里我们都按照升序来讲解
2. 堆排序基本思路🚩
基本思路:
- 建立一个大堆(升序建大堆)
- 将堆顶元素与最后一个元素交换
- 交换后堆元素减一,重新调整堆
具体为什么要这样做后面会解释.
我们现在先模拟一次循环的实现:
假设现在有一个大堆是这样的:
它在数组中的物理结构存储是
关键的地方来了:
将堆顶元素70与最后一个元素10交换
交换后最后一个位置就不变了
因为它就是这个数组中的最大值
再将剩下的数组元素重新变成大堆
这一次循环过后
我们就把数组中最大值放到最后一个位置
下一次循环把倒数第二大值
放在倒数第二个位置
以此类推直到将数组变成有序的
3. 把一个数组变成大堆的思考🚩
问题研讨:
在现实遇见排序问题时不会给你一个大堆.
怎样把任意数组变成大堆?
并且每次排完最大值后
怎样将剩下的数组重新建立成大堆?
问题解决思路:
在之前堆的学习中,删除数据是将头尾交换
删除尾后再向下调整,使整个数组又变成堆
这里引申出的结论:
- 对一个大堆向下调整的前提是:
当前节点的左右分支都是大堆 - 对一个小堆向下调整的前提是:
当前节点的左右分支都是小堆
解决办法:
倒着向上使用向下调整
从第一个非叶子节点开始
比如我们任意定义一个数组:
int a[10]={70,56,30,25,15,10,75,33,50,69}; • 1
它的物理结构是一个数组
逻辑结构可以看作堆:
我们边做边画图:
1. 第一步:
- 从序号5开始向下调整.
- 使序号5,10所在的分支变成大堆
2. 第二步:
- 从序号4开始向下调整.
- 使序号4,8,3所在的分支变成大堆
3. 第三步:
- 从序号2开始向下调整
- 使序号2.4.5.8.9.10组成的分支变成大堆
4. 第四步:
- 从序号3开始向下调整
- 使序号为3.6.7的分支变成大堆
5. 最后一步
- 从序号1开始向下调整
- 将整个数组的逻辑结构改成大堆!
4. C语言代码实现🚩
分两步走:
- 将数组建立成大堆:(n为数组长度)
for(int i = (n - 1 - 1) / 2;i>=0;i--) { AdjustDown(a,n,i); }
- 对代码的解释:
i = n-1-1的n-1代表最后一个元素的下标
它的父亲节点是(child-1)/2. 刚好第一次
调整就是从最后一个元素的父亲开始的.
向下调整函数AdjustDown在堆详解中
- 依次选数再调整堆
for(int end = n-1;end>0;end--) { //先交换 Swap(&a[end],&a[0]); //再调堆 Adjustdown(a,end,o); }
- 对代码的解释:
end的从指向元素末尾不断减一
保证每次选出的最大数不受后面操作影响
5. 堆排序时间复杂度分析🚩
1. 建堆的时间复杂度:
我们按最坏的情况来计算:
即:堆为满二叉树并且
每次向下调整都走最远的距离
所有节点移动的总次数:
这里需要用到高中学的错位相减法求T(h)
T (h)=20× (h-1) + 21×(h-2) +…+2(h-2)×1
2T(h)=21×(h-1) + 22×(h-2) +…+2(h-1) ×1
两式相减得T(h) = 2h - 1 - h.
时间复杂度是关于节点个数n的
n和h有换算关系: n=2h-1
最终得到:
T(n) = n - log2(n+1) ≈ n
时间复杂度: O(n)
2. 选数调堆时间复杂度:
调堆时,每选出一次最大值交换
就要向下调整高度次:(log2n次)
一共需要选n-1次数,相乘得:
时间复杂度: O(n×log2n)
这两个for循环不是嵌套关系
所以堆排序总时间复杂度为:O(N)
6. 思考总结以及拓展🚩
思考:为什么排升序要建大堆?
假如我们建立小堆:
- 在小堆中选出最小得数放在第一个位置
- 如何选出次小的数?
拿我们上面举例的数组说明:
从15位置开始,剩下的数看做一个堆
但是在这之前建立好的堆关系全部乱了
需要重新建堆才能选出次小数!
总结:
建立小堆排升序是可以的
但是效率很低没有体现优势
看似这里的代码量很少
但其中的思想还是比较复杂的
经常有人看见这么少的代码量
就觉得自己背下来就能会.
实际上面试是考思想,不是考死记硬背!
让我们回到罗伯特·弗洛伊德这个传奇人物
他原本是在芝加哥大学搞文学的
奈何毕业时正巧美国经济不景气
靠搞文学的收益可谓是少中又少
于是他去了一家电气公司当小职员
干了一段时间他对计算机产生了浓厚兴趣
他通过自学,旁听的方式理科学士学位
而且从一个计算机门外汉变成计算机行家
并且在1980年获得了图灵奖(梦中情奖)
这梦幻的一生着实让人羡慕
🔎 下期预告:快速排序 🔍
