堆排序不稳定举例
墨初 知识笔记 132阅读
堆排序有难度吗？
答：堆排序是很有难度的算法。 搞懂之后就觉得，"还行吧"。 先讲个故事: 周日学校有开个实习的招聘会，没有拿到大公司offer的我，当然约上舍友走起啦。 第一家，有人在面试了，那我就在旁边听下，只记得，"你会快排吗?
什么是稳定排序？
答：我了解稳定排序的重要性-它使我们能够基于多个键进行排序，这非常有益 (例如，进行多种排序，每种排序均基于不同的密钥。 由于每种排序都会保留元素的相对顺序， 以前的排序可以加起来，以给出按多个条件排序的元素的最终列表)。
什么是堆排序算法？
答：其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。 由于交换后新的堆顶R [1]可能违反堆的性质，因此需要对当前无序区 (R1,R2,......Rn-1)调整为新堆，然后再次将R [1]与无序区最后一个元素交换，得到新的无序区 (R1,R2....Rn-2)和新的有序区 (Rn-1,Rn)。 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成 下图来张教材的图，是整个堆排序的过程: 整个过程的核心就是先初始化大顶堆，将最大数 (堆顶)的放到堆的最后一个, 堆长度-1, 继续调整成大顶堆，直至有序序列为len (array_list)-1.
在长为n 的序列中,堆排序过程是怎么回事？
答：在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大 (大顶堆)或者最小 (小顶堆),这3个元素之间的选择当然不会破坏稳定性。 但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。