堆排序
堆排序是利用堆这样的数据结构而设计的一种排序算法，堆排序是一种选择排序。
堆排序思想：
- 将待排序列构造成成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点；
- 将其与末尾元素进行交换，此时尾值就是最大值；
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
- 反复进行操作，就会得到一个有序序列。
二叉树的定义：
二叉树是每个节点最多有两个子节点的树结构。
二叉树的特点： - 每个节点最多有两个子节点，也就是说二叉树不存在大于2的节点；
- 二叉树的子树有左右之分，其子树的顺序不能颠倒。
二叉树结构示意图：
对于堆来说需要满足一下两个条件： - 是一个完全二叉树
- 所有父节点的值都要大于（或小于子节点的值）
在堆排序中，大顶堆排序是将最值也就是大顶堆最上面的第一个值，每一次将该值取出，最后得到一个有序的数组。
第一个大顶堆，代码图示：
代码展示+注释（第一个大顶堆）：
//堆排序
public static void main(String[] args) {
int[] arr = {98,25,32,45,62,31,45,63,77};
//调用大顶堆的方法
//toMaxHeap(arr,arr.length,1);
//定义开始调整的位置
int startIndex = (arr.length-1)/2;
//循环开始调
for (int i = startIndex; i >= 0; i--) {
toMaxHeap(arr, arr.length, i);
}
System.out.println(Arrays.toString(arr));
}
/**
*
* @param arr 表示需要排序的数组
* @param size 调整的元素个数
* @param index 从什么地方开始调整
*/
private static void toMaxHeap(int[] arr, int size, int index) {
// 获取左右节点的索引
int leftNodeIndex = index*2+1;//左节点的索引
int rightNodeIndex = index*2+2;//右节点的索引
//查找最大节点所对应的索引
int maxIndex = index;
if (leftNodeIndex<size && arr[leftNodeIndex]>arr[maxIndex]) {//注意这里前面的一个条件，否则可能会出现角标越界
maxIndex = leftNodeIndex;
}
if (rightNodeIndex<size && arr[rightNodeIndex]>arr[maxIndex]) {//注意这里前面的一个条件，否则可能会出现角标越界
maxIndex = rightNodeIndex;
}
//找出最大索引后，这时需要交换位置
if (maxIndex!=index) {
int temp = arr[maxIndex];
arr[maxIndex] = arr[index];
arr[index] = temp;
//调换完之后可能会影响到下面的字树，不是大顶堆，还需要再次进行调换
toMaxHeap(arr, size, maxIndex);
}
}
在上面的图示中我们可以发现，这就是一个大顶堆，如下图所示：
最终效果展示以及代码！
代码图示：
代码+注释：
//堆排序
public static void main(String[] args) {
int[] arr = {98,25,32,-1,45,62,31,45,63,77,99};
//调用大顶堆的方法
//toMaxHeap(arr,arr.length,1);
//定义开始调整的位置
int startIndex = (arr.length-1)/2;
//循环开始调
for (int i = startIndex; i >= 0; i--) {
toMaxHeap(arr, arr.length, i);
}
//System.out.println(Arrays.toString(arr));//在成大顶堆的第一个输出
//经过上述的操作已经编写出了一个大顶堆，接下来把根元素与最后一个元素进行调换
for(int i = arr.length-1;i>0;i--){
//开始进行调换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//在调完之后，再把剩余元素调成大顶堆
toMaxHeap(arr,i, 0);
}
System.out.println(Arrays.toString(arr));
}
/**
*
* @param arr 表示需要排序的数组
* @param size 调整的元素个数
* @param index 从什么地方开始调整
*/
private static void toMaxHeap(int[] arr, int size, int index) {
// 获取左右节点的索引
int leftNodeIndex = index*2+1;//左节点的索引
int rightNodeIndex = index*2+2;//右节点的索引
//查找最大节点所对应的索引
int maxIndex = index;
if (leftNodeIndex<size && arr[leftNodeIndex]>arr[maxIndex]) {//注意这里前面的一个条件，否则可能会出现角标越界
maxIndex = leftNodeIndex;
}
if (rightNodeIndex<size && arr[rightNodeIndex]>arr[maxIndex]) {//注意这里前面的一个条件，否则可能会出现角标越界
maxIndex = rightNodeIndex;
}
//找出最大索引后，这时需要交换位置
if (maxIndex!=index) {
int temp = arr[maxIndex];
arr[maxIndex] = arr[index];
arr[index] = temp;
//调换完之后可能会影响到下面的字树，不是大顶堆，还需要再次进行调换
toMaxHeap(arr, size, maxIndex);
}
}