目录
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
个人愚见,欢迎各位朋友斧正.