详解如何在Java中实现堆排序算法
作者:之一Yo 时间:2023-11-11 11:34:46
算法描述
堆排序算法的描述如下:
将待排序的数组调整为最大堆,此时未排序的长度
N
为数组的长度,调整的过程就是倒序将数组的前N/2
个元素下沉的过程,每次下沉都会将较大的元素带到上面,最终将数组变为最大堆;弹出最大堆的堆顶元素并将其移动到数组的最后面,将原本最后面的元素放到堆顶,然后将未排序的长度
N
- 1,调整数组的前N
个元素为最大堆;重复步骤 2 直到未排序的长度为 0.
实现代码
package com.zhiyiyo.collection.sort;
import java.util.Arrays;
public class HeapSort extends BaseSort {
@Override
public void sort(Comparable[] array) {
int N = array.length;
// 创建最大堆
for (int i = N / 2; i >= 0; i--) {
sink(array, i, N);
}
// 就地排序
while (N > 0) {
// 将最大的元素移动到数组的尾部,同时将未排序的长度-1
swap(array, 0, --N);
// 调整最大堆
sink(array, 0, N);
}
}
/**
* 下沉元素
*
* @param array 数组
* @param k 下沉的元素索引
*/
private void sink(Comparable[] array, int k, int N) {
while (2 * k + 1 < N) {
int j = 2 * k + 1;
if (j < N - 1 && less(array[j], array[j + 1])) j++;
if (!less(array[k], array[j])) break;
swap(array, k, j);
k = j;
}
}
}
抽象类 BaseSort
的代码为:
package com.zhiyiyo.collection.sort;
/**
* 数组排序抽象类
*/
public abstract class BaseSort {
public abstract void sort(Comparable[] array);
/**
* 交换数组元素
*
* @param array 数组
* @param a 数组下标 a
* @param b 数组下标 b
*/
protected static void swap(Comparable[] array, int a, int b) {
Comparable tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
protected static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
}
测试代码
package com.zhiyiyo.collection.sort;
import org.junit.Test;
import java.util.Arrays;
public class HeapSortTest {
@Test
public void sort() {
Integer[] array = {5, 10, 9, 6, 8, 7, 2, 1, 4, 3};
new HeapSort().sort(array);
System.out.println(Arrays.toString(array));
}
}
最终排序结果为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],以上~
来源:https://www.cnblogs.com/zhiyiYo/p/16042137.html
标签:Java,堆排序
0
投稿
猜你喜欢
springboot嵌套子类使用方式—前端与后台开发的注意事项
2023-09-16 12:37:22
C#导出数据到CSV文件的通用类实例
2023-05-22 09:23:16
Mybatis对mapper的加载流程深入讲解
2022-06-01 12:33:04
Java日常练习题,每天进步一点点(41)
2023-05-18 18:10:02
Spring的组合注解和元注解原理与用法详解
2023-12-05 10:25:05
深入解读Android的内部进程通信接口AIDL
2022-09-09 04:02:02
基于序列化存取实现java对象深度克隆的方法详解
2021-08-31 07:45:26
详解C#中三个关键字params,Ref,out
2021-09-25 18:54:02
Android分屏多窗口的实践代码
2021-06-21 21:34:58
Java实现中英文词典功能
2021-06-20 18:25:56
C语言安全编码之数组索引位的合法范围
2021-12-08 06:09:51
spring mvc 组合mybatis框架实例详解
2023-11-28 04:56:04
基于SpringBoot生成二维码的几种实现方式
2022-02-27 16:24:31
Java详细分析梳理垃圾回收机制
2023-10-30 04:02:33
RxJava 触发流基本原理源码解析
2023-06-24 06:02:57
Unity实现游戏卡牌滚动效果
2023-09-20 10:54:23
使用itextpdf操作pdf的实例讲解
2022-11-16 00:22:43
Java 你知道什么是耦合、如何解(降低)耦合
2022-03-23 08:44:19
java编程中字节流转换成字符流的实现方法
2021-06-09 15:59:04
java读取csv文件内容示例代码
2023-03-13 22:09:14