如何在 Java 中实现堆排序算法
2023-02-18 16:31:00 时间
算法描述
堆排序算法的描述如下:
- 将待排序的数组调整为最大堆,此时未排序的长度
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],以上~
相关文章
- 我以订披萨为例,给女朋友详细讲了Java设计模式的3种工厂模式
- 【架构师(第二十五篇)】编辑器开发之属性编辑区域表单渲染
- 【架构师(第二十六篇)】编辑器开发之属性编辑同步渲染
- 2021年度“CCF-腾讯犀牛鸟基金”发布结题评优结果
- 【架构师(第二十七篇)】前端单元测试框架 Jest 基础知识入门
- 太空噗|重燃太空热潮!与噗噗星人一同探索星海浪漫
- 算法工程师深度解构ChatGPT技术
- 【架构师(第二十八篇)】 测试工具 Vue-Test-Utils 基础语法
- 【架构师(第二十九篇)】Vue-Test-Utils 触发事件和异步请求
- 【架构师(第三十篇)】Vue-Test-Utils 全局组件和第三方库 vuex | vue-router
- 【架构师(第三十一篇)】前端测试之 TDD 的开发方式
- 【架构师(第三十二篇)】 通用上传组件开发及测试用例
- 【架构师(第三十三篇)】 Vue 中的实例及本地图片预览
- 【架构师(第三十四篇)】 业务组件库开发之 vue3 的插件系统
- 【架构师(第三十五篇)】 业务组件库开发之使用 Rollup 进行打包
- 【架构师(第三十六篇)】 业务组件库开发之发布到 NPM
- 【架构师(第四十二篇)】 服务端开发之常用的登录鉴权方式
- 【架构师(第四十三篇)】 服务端开发之单元测试和接口测试
- 【架构师(第四十四篇)】 服务端开发之 pm2 和 nginx 介绍
- 【架构师(第四十六篇)】 服务端开发之安装 Docker