排序算法之堆排序

一、介绍

由于堆排序与以前的排序都不太一样,他是基于顺序存储的二叉树结构来进行的排序,故此拉出来单独做了一张。

以前的排序算法传送门

二、概念

在开始编码之前,我们先要理解下面两个概念

1)顺序存储的二叉树

对于任意一个数组,它都可以转换为一个完全二叉树

如下图,平铺着转换就可以了

image-20220929134325874

对于一个顺序存储的二叉树,它的节点连接定义如下

下标N的左节点2n+12n+1

下标N的右节点2n+22n+2

下标N的父节点n12\frac{n-1}{2}

2)大小顶堆

什么是大顶堆,就是父节点永远都比子节点的数要大,故名为大顶堆。如下图

image-20220929134447486

相反,如果一颗二叉树的父节点都比子节点的数要小,那么它就是小顶堆。如下图

image-20220929134405141

三、代码

简单的来说,堆排序就是将持续的将,一个顺序存储的二叉树变成大顶堆或者小顶堆。

升序使用大顶堆,降序使用小顶堆。

步骤如下,这是第一步

  1. 从非叶子节点开始前遍历

  2. 每一个非叶子节点,都将和自己的左节点、右节点进行判断

  3. 根据大小顶堆的需要,来进行替换

  4. 直到称为一个大小顶堆

成为了大小顶堆之后,我们将得到了一个最大或者最小的数,也就是大小顶堆根节点的数

  1. 将这个根节点与最后的叶子节点进行替换,也就是将最大或者最小的数放到了最后

找到了一个数还不够,我们将重复上面的步骤

  1. 重复第一步,但不要影响放到最后的数

  2. 得到大小顶堆的根节点后,进行替换,不是和最后的数进行替换了,而是依次往前替换。

  3. 直到排序玩成

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.banmoon.algorithm.order;

import java.util.Arrays;

/**
* 堆排序
*/
public class Demo08 {

public static void main(String[] args) {
// int[] arr = {128, 359, 26, 78, 98, 5, 789, 12, 6, 2};
int[] arr = {2, 9, 7, 8, 3, 5, 4, 1, 6, 0};
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}

private static int[] sort(int[] arr) {
// 先进行一次大顶推的转换
int last = (arr.length - 1) / 2;
for (int i = last; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
// 将这个根节点与最后的叶子节点进行替换,也就是将最大的数放到了最后
for (int i = arr.length-1; i > 0; i--) {
// 替换最前和最后的数
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 替换后,需要将根节点的数进行一次转移,重新变为大顶堆
maxHeap(arr, i, 0);
}
return arr;
}


public static void maxHeap(int[] arr, int size, int index){
// 左节点
int leftIndex = index*2+1;
// 右节点
int rightIndex = index*2+2;
// 和左右节点进行对比
int max = index;;
if(leftIndex < size && arr[leftIndex] > arr[max])
max = leftIndex;
if(rightIndex < size && arr[rightIndex] > arr[max])
max = rightIndex;
// 进行交换
if (max != index) {
int temp = arr[max];
arr[max] = arr[index];
arr[index] = temp;
// 交换位置后,需要再对替换的index向下判断
maxHeap(arr, size, max);
}
}

}

image-20220929153725892

四、最后

堆排序是常规排序的最后一块拼图,像后面还有许多高阶的排序算法,菜鸟的我估计是用不上了。

如果有兴趣,以后可以研究学习一下。

我是半月,祝你幸福!!!