大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、什么是堆排序
1.堆,堆排序
对于“堆”我们可以理解为具有以下性质的完全二叉树:
- 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆
- 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
在排序时,一般升序采用大顶堆,降序采用小顶堆。
2.大顶堆
我们可以看到,层数从小到大,节点的数字是越来越小的,映射到数组有:{50,45,40,20,25,35,30,10,15}
特点是arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
3.小顶堆
跟大顶堆相反,层数从小到大,节点的数字是越来越大,映射到数组:{10,20,15,25,50,30,40,35,45}
特点是:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
二、堆排序的思路分析
1.概述
- 将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换,此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。
- 遍历构建大顶堆,在这过程中元素的个数逐渐减少,直到最后得到一个有序序列了.
2.举个例子
对数组{4,6,8,5,9}进行排序。
第一遍排序
-
我们从最后一个非叶子结点开始排序。第一个非叶子结点为
arr.length/2-1=5/2-1=1
,也就是元素6.,我们对他进行对比并调整位置; -
在{6,5,4}中,5比6小,而9比6大,所以9和6交换位置;
-
接着找到第二个非叶子节点4,由于9是{9,4,8}这个树中最大的,故9与4交换位置
-
由于9与4交换位置打乱了原先{9,5,6}这棵树顺序,所以继续对新树{4,5,6}进行排序
-
由此得到了一个大顶堆,然后将堆顶元素9与末尾元素4进行交换,得到数组{4,6,8,5,9}
至此,第一遍排序已经完成,我们确定了最大元素9的位置
第二遍排序
第二遍排序开始时,最大元素9的位置已经确定,实际上要排序的数组变成了{4,6,8,5}
-
继续从6开始比较,{6,5}排序正常,所以接着比较{4,6,8},8是最大的,所以与4交换位置
-
由此得到了一个大顶堆,然后将堆顶元素8与末尾元素5进行交换,得到数组{8,6,4}
至此,第一遍排序已经完成,我们确定了最第二大元素8的位置
第三遍~第n遍排序
第二遍排序开始时,最大元素9和第二大元素8的位置已经确定,实际上要排序的数组变成了{5,6,4}
重复比较-排序-交换堆顶和队尾元素位置这一过程,直到最终获得有序数列
三、代码实现
/**
* @Author:CreateSequence
* @Date:2020-07-16 16:53
* @Description:堆排序
*/
public class HeapSort {
/**
* 对数组进行堆排序
* @param arr
* @return
*/
public static int[] sort(int[] arr) {
//将无序数组构建成一个大/小顶堆
//有几个非叶子节点就排序几次
for (int i = arr.length / 2 - 1; i >= 0; i--) {
sortHeap(arr,i,arr.length);
}
int temp = 0;
//交换数组头尾元素,将最大的元素排沉到队尾
for (int i = arr.length - 1; i > 0; i--) {
//交换头尾元素
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//1.交换完后,此时最大的元素在arr[0],最小的元素在arr[i],即确定了本次排序范围最大的数
//2.然后对0~i-1的范围进行排序,重新获得的数组最小的元素在arr[0],最大的元素在arr[i-1]
sortHeap(arr, 0, i);
//3.接着进入下一次循环,重复步骤1,2,每次循环排序范围都缩小一位
}
return arr;
}
/**
* 将以非叶子节点i为根节点的树调整为一个大顶堆
* @param arr 要调整的数组
* @param i 非叶子结点在数组中的下标
* @param length 要调整的数组长度
*/
public static int[] sortHeap(int[] arr, int i, int length) {
if (arr == null || arr.length == 0) {
throw new RuntimeException("数列必须至少有一个元素!");
}
//获取根节点值
int temp = arr[i];
//从左节点开始遍历
for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
//比较左右节点大小,将j指向值大的节点
if (j + 1 < length && arr[j + 1] > arr[j]) {
j = j + 1;
}
//比较将左右节点与父节点大小
if (arr[j] > temp) {
//如果子节点大于父节点,交换两节点位置
arr[i] = arr[j];
//然后继续从该子节点向下遍历
i = j;
}else {
break;
}
}
//结束循环时,arr[i]已经存放了以原arr[i]为根节点的树的最大值
arr[i] = temp;
return arr;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170805.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...