在思想方面讨论堆排序(考研自用,按非递减方式排序)

 


目录
1.什么是排序
2.关于堆排序的几个问题
3.问题求解
首先:排序的定义

 

 


拿冒泡排序(递增)来讲,在一个给定的数组序列中,若A[i+1]<A[i],则将其两个的数值进行交换,排好序的序列应该是递增的,类似于[1,2,3,4,5...];

所以排序是在数组中进行的,物理内存的数值发生了永久性的变化(和初始状态不相同了).

其次,知道什么是排序之后再了解什么是堆排序

 


很明显,这里提出了两个问题,1 怎么构成初始堆,2 如何调整输出后的堆

第一个问题比较好理解,但是第二个问题为什么要输出堆顶元素,输出的堆顶元素用来做什么了?

这个问题涉及到本题目的迷惑我挺长时间的解题步骤:到底使用大根堆还是小根堆?

为什么不能用大/小根堆?

通常来讲,排序不涉及到直接输出的问题,或者是说要输出排好序的数组序列

所以第二个问题就迎刃而解了,不需要输出堆顶元素,我排好序之后整个数组序列就是题目想要的答案.除非题目要求我输出堆顶元素.

最后,针对这道题的解法
要求是按照非递减的方式进行排序,由于给定的数值没有相同的,因此非递减的含义就变成了递增.

如果使用小根堆的方式:

 

最后的数组排序将是逆序

但是使用大根堆的方式:

 

 

 

调整后的数组排序将是递增的.

因此建立的初始堆即是:

相应的就能解释为什么第二题第一次交换之后的关键码是 45 90 26 61 72 11 4 97(第一次交换指的是堆顶元素和堆底元素的交换=>相当于输出/删除堆顶元素 然后剩下的元素重新调整),所以重新建立的大根堆应该是:

            90

    72            26

61   45        11    4

 

 

90 72 26 61 45 11 4

个人愚见,欢迎各位朋友斧正.

热门相关:国破山河在   龙骑战机   国破山河在   至尊剑皇   国破山河在