堆排序——Java实现
2021/5/19 14:26:01
本文主要是介绍堆排序——Java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、堆排序
堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
二、堆
-
什么是堆
堆是一个树形结构,其实堆的底层是一棵完全二叉树。而完全二叉树是一层一层按照进入的顺序排成的。按照这个特性,我们可以用数组来按照完全二叉树实现堆。 -
大顶堆与小顶堆
大顶堆原理:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大顶堆。大顶堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。
小顶堆原理:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者,称为小顶堆。小堆堆要求根节点的关键字既小于或等于左子树的关键字值,又小于或等于右子树的关键字值。
三、推排序思想
- 构建初始堆,将待排序列构成一个大顶堆(或者小顶堆),升序大顶堆,降序小顶堆;
- 将堆顶元素与堆尾元素交换,并断开(从待排序列中移除)堆尾元素。
- 重新构建堆。
- 重复2~3,直到待排序列中只剩下一个元素(堆顶元素)。
四、图解
五、代码实现
/** * 堆排序演示 * * @author Lvan */ public class HeapSort { public static void main(String[] args) { // int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; int[] arr = {16, 7, 3, 20, 17, 8}; heapSort(arr); for (int i : arr) { System.out.print(i + " "); } } /** * 创建堆, * @param arr 待排序列 */ private static void heapSort(int[] arr) { //创建堆 for (int i = (arr.length - 1) / 2; i >= 0; i--) { //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr, i, arr.length); } //调整堆结构+交换堆顶元素与末尾元素 for (int i = arr.length - 1; i > 0; i--) { //将堆顶元素与末尾元素进行交换 int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //重新对堆进行调整 adjustHeap(arr, 0, i); } } /** * 调整堆 * @param arr 待排序列 * @param parent 父节点 * @param length 待排序列尾元素索引 */ private static void adjustHeap(int[] arr, int parent, int length) { //将temp作为父节点 int temp = arr[parent]; //左孩子 int lChild = 2 * parent + 1; while (lChild < length) { //右孩子 int rChild = lChild + 1; // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点 if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } // 如果父结点的值已经大于孩子结点的值,则直接结束 if (temp >= arr[lChild]) { break; } // 把孩子结点的值赋给父结点 arr[parent] = arr[lChild]; //选取孩子结点的左孩子结点,继续向下筛选 parent = lChild; lChild = 2 * lChild + 1; } arr[parent] = temp; } }
这篇关于堆排序——Java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现