堆排序基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
- 要理解堆排序,必须先要理解堆这种数据结构
堆是具有以下性质的完全二叉树:
- 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
- 大顶堆示意图:
我们对堆中的结点按层进行编号,映射到数组中就是下面这个样子:
大顶堆特点:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 对应第几个节点,i从0开始编号
注意:这里需要先理解顺序存储二叉树的知识,可以参考我的文章顺序存储二叉树
- 小顶堆示意图:
小顶堆:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 对应第几个节点,i从0开始编号
- 一般升序采用大顶堆,降序采用小顶堆
堆排序基本思想
堆排序的基本思想是:
- 将待排序序列构造成一个大顶堆
- 此时,整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换,此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。
可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了
堆排序思路和步骤:
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)
-
假设给定无序序列结构如下
-
此时我们从数组的最后一个非叶子结点(即下标为arr.length/2-1)开始(叶结点自然不用调整,最后一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从右至左,从下至上进行调整。
-
找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。
-
这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。
此时,我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。
-
将堆顶元素9和末尾元素4进行交换
-
重新调整结构,使其继续满足堆定义
- 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8
- 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序
堆排序的代码实现
堆排序的代码不是很好理解,代码里面有详细注释,可以仔细阅读代码注释加深对堆排序理解
public class HeapSort {
public static void main(String[] args) {
int[] array = new int[80000];
for (int i = 0; i < array.length; i++) {
// 随机生成一个0到8000000的随机数
Random random = new Random();
int nextInt = random.nextInt(8000000);
array[i] = nextInt;
}
// 排序前时间,h毫秒
long beforeSortTimeMillis = System.currentTimeMillis();
heapSort(array);
// 排序后时间
long afterSortTimeMillis = System.currentTimeMillis();
System.out.println("排序80000个数据总共花费时间为:" + (afterSortTimeMillis - beforeSortTimeMillis) + "毫秒");
int[] arr = {4,6,8,5,9,74,1,45,23,46,26,26}; // 调整成大顶堆为 9,6,8,5,4
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 按堆排序,把数组变成一个升序的数组
* @param array
*/
public static void heapSort(int[] array) {
// 把该数组看成一个顺序存储的二叉树,升序排序,先把该数组调整成一个大顶堆,
// 调整成大顶堆,先从该顺序二叉树的最后非叶子节点开始调整,从右到左,从下到上
// 最后一个非叶子节点的 下标为 array.length/2-1
for (int i = array.length/2-1; i >= 0; i--) {
adjustHeap(array,i,array.length);
}
// 代码走到这该数组已经是一个大顶堆,头结点是最大值,即数组的第一个元素是最大值
// 把该数组的头节点与末尾交换,然后把除去数组末尾的数继续调整成大顶堆
for (int n = array.length - 1; n > 0 ; n--) {
int temp = array[0];
array[0] = array[n];
array[n] = temp;
// 然后把该数组的从下标为0开始,长度为n的数组继续调整成一个大顶堆
// 即以数组的第一个元素为根节点开始调整,
// 因为以array[0]根节点的树,该树下面的每一颗子树都已经是大顶堆了
// 参考到adjustHeap()方法的作用,所以可以直接调用该方法,
// 把array[0]调整到该树合适的位置,让该树继续是一个大顶堆
adjustHeap(array,0,n);
}
}
/**
* 该方法总的作用是把以array[i]为根节点的树的头节点array[i]按大小调整到其合适的位置,从上往下,逐层比较,最后找打array[i]合适的位置
* 1.该方法把以下标为i的数作为根节点的树调整成一个大顶堆,
* 2.要满足1,必须先把以arrry[i]为根节点的树下面的每一颗树都必须先调整成一个大顶堆,
* 3.也就是想要把以array[i]为根节点的数调整成大顶堆,必须要循环调用该方法,
* 先从该树的最后一个非叶子节点开始递减调整,才能把该树调整成一个大顶堆
* @param array 看做一个顺序存储的二叉树的数组
* @param i 以i为根节点数
* @param length 要调整的数组长度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先保存该根节点
int temp = array[i];
// 左子节点 i*2+1 右子节点 i*2+2
// 循环遍历,使k指向左子节点,每次循环在指向下一个左子节点
// 该循环中右2个变量需要理解,i是父节点,k是其子节点,注意i和k的变化,可以理解成指针
for (int k = i*2+1; k < length; k=k*2+1) {
// 比较左右节点的大小,如果右节点大于左节点就让k指向右节点
if (k+1 < length && array[k+1] > array[k]) {
k++;
}
// 在比较初始根节点的值(即保存在temp的值)和array[k](即左右节点中较大的那个值)的大小
if (array[k] > temp) {
// 如果大于则把该左右节点较大的值赋值给其父节点
array[i] = array[k];
// 让i指向k,即让i移动到左右节点中较大那个节点,然后继续循环下一次
i=k;
} else {
// 代码走到这说明,该左右子节点的较大值不大于该树的原始根节点(即temp,)
// 也就不用继续比较下去了,头节点已经找到其合适的位置,循环终止退出
break;
}
}
// 代码执行到这,说明已经找到合适的位置即下标为i的位置,最后把头节点的值放到到他合适的位置
array[i] = temp;
}
}
运行结果:
排序80000个数据总共花费时间为:8毫秒
[1, 4, 5, 6, 8, 9, 23, 26, 26, 45, 46, 74]
从结果可以看出堆排序是非常快的,排序80000个数据才用了8毫秒,堆排序的事件复杂度是O(nlogn)
对以上代码再次说明:
- 以上代码中要理解方法
adjustHeap()
方法的作用,该方法并不是把传入的一个数组变成大顶堆,而是结合heapSort()
方法中的代码:for (int i = array.length/2-1; i >= 0; i--) {
adjustHeap(array,i,array.length);
}
当这段for循环结束,才会把数组变成一个大顶堆
- 然后
heapSort()
方法下的代码:for (int n = array.length - 1; n > 0 ; n--) {
int temp = array[0];
array[0] = array[n];
array[n] = temp;
// 然后把该数组的从下标为0开始,长度为n的数组继续调整成一个大顶堆
// 即以数组的第一个元素为根节点开始调整,
// 因为以array[0]根节点的树,该树下面的每一颗子树都已经是大顶堆了
// 参考到adjustHeap()方法的作用,所以可以直接调用该方法,
// 把array[0]调整到该树合适的位置,让该树继续是一个大顶堆
adjustHeap(array,0,n);
}
此代码的作用是把数组头元素和尾元素进行交换,然后继续调用adjustHeap()
把头元素调整到合适位置,让除去已找到最大值的数组继续是一个大顶堆,在交换如此反复执行,直到数组是一个有序数组。