堆排序
程序员文章站
2022-06-06 20:55:23
...
堆排序
算法描述：
堆排序是利用数据结构中堆的特性完成排序的算法。堆的定义：堆可以看成是一个完全二叉树，又有一定特性，父节点都大于或小于左右子节点。数学式子表示：
1. 若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：
任意一节点指针 i：父节点：i==0 ? null : (i-1)/2
左孩子：2*i + 1
右孩子：2*i + 2
2. 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；
我们此处以大根堆(也叫大顶堆)的特性来进行排序，经过一次堆调整后，根节点就是这个序列的最大值，根节点与最后一个叶节点交换位置，取出根节点放到Array[n-1]的位置，再进行一次堆调整，根节点是剩下的n-1个数列中最大的值，再与最后一个叶节点交换位置，取出这个值存入Array[n-2]的位置，依照上面的方法进行循环即可得到最后的数组就是一个升序的数组。
时间复杂度：o(n*logn)
空间复杂度：o(1)
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
java代码：
public static void heapSort(int[] arr) {
int l = arr.length;
for (int i = 0; i < l - 1; i++) {// 循环调用建立堆函数建立堆
buildHeap(arr, l - 1 - i);// 调用建立堆函数
swap(arr, 0, l - 1 - i);// 堆建立好后，交换根节点和堆的最后一个节点，每一次堆构建都会选出最大值
}
}
public static void buildHeap(int[] a, int lastIndex) {
for (int j = (lastIndex - 1) / 2; j >= 0; j--) {// 从lastIndex节点（最后一个节点）的父节点开始循环
int k = j;// k保存正在判断的节点
// 如果当前k节点的子节点存在，一个堆调整之后有可能影响其他堆，所以还有遍历子节点的堆
while (2 * k + 1 <= lastIndex) {
int biggerIndex = 2 * k + 1;// k节点的左子节点索引
if (biggerIndex < lastIndex) {// 表示k节点存在右节点
if (a[biggerIndex] < a[biggerIndex + 1]) {// 与右节点比较
biggerIndex++;// biggerIndex总是记录较大子节点的索引
}
}
if (a[k] < a[biggerIndex]) {// 如果k节点的值小于较大子节点的值，则交换它们的值，并将biggerIndex赋值给k，开始下一次循环
swap(a, k, biggerIndex);// 保证k节点的值大于其子节点的值
k = biggerIndex; // 关键赋值，进行下一次的遍历比较
} else {
break;
}
}
}
}
public static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}