堆排序 选择排序的升级
选择排序的思想是每次选择未排序列中最小值的下标,使它对应的值与未排序数列中第一个的值交换内容。从而达到选择的目的。
而堆排序就是每次调整后,选出最大值在堆顶,然后使堆顶放入数列末尾,然后数列长度减1,
这样就总使未排数列中的最大值放在未排数列的最后一位。
然而怎么确定数列中最大的数呢,如果遍历未排数列 一个一个去比,那显然就是一般的选择排序了
但我们要升级,我们要牛逼,我们要高大上,其实最重要的还是减少操作。
因此引入了堆 或者叫二叉树的方法。
堆的思想是什么呢,抽象点说什么左子树和右子树和 树根的什么关系 2 *i 2*i+1之类的显然不是人话。
那干脆就简单点,实干点。你先把一个数列按大树的形状挨个排下来。自己找找规律看
二叉树和排序有什么关系呢?当然有关系!
我们可以看到目前二叉树是完全乱序的,意思就是树根和子树没有大小关系,我们要做的就是调整,调整的目标就是让所有树根都比它的子树们大!这样调整下来的结果就是堆顶,总跟,变为最大的数。这就是我们所要的东西!未排序列中最大的数(或最小的数)。然后让最大数放到堆底最后一个,使堆总长度-1. 反复循环这一步,那不就全部有序了吗?
以下是代码:
时间复杂度均为 O(nlog2n)
稳定性是不稳定的。一旦一层数字调整了发生了向上交换,那就跳跃式交换数据了,无法保证相同的值的位置关系