写一个java的堆排序

时间: 2023-07-06 18:34:07 浏览: 30
好的,请看以下代码: ```java public class HeapSort { public static void sort(int[] arr) { int n = arr.length; // 构建一个大根堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 逐步取出堆顶元素,放到数组末尾,再进行堆化 for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); } } // 堆化操作,将以index为根的堆调整为大根堆 public static void heapify(int[] arr, int n, int index) { int largest = index; // 初始化最大值为根节点 int left = 2 * index + 1; // 左子节点的下标 int right = 2 * index + 2; // 右子节点的下标 // 找出左右子节点中的最大值 if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; // 如果最大值不是根节点,则交换根节点和最大值,并继续堆化操作 if (largest != index) { swap(arr, index, largest); heapify(arr, n, largest); } } // 交换数组中的两个元素 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ``` 这里我们首先构建一个大根堆,然后每次将堆顶元素(即最大值)放到数组末尾,再对剩余的元素进行堆化操作,使其重新满足大根堆的定义。最终得到的数组就是排好序的。

相关推荐

### 回答1: 好的,以下是一个简单的Java冒泡排序的示例代码: public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 2, 8, 4, 9}; // 冒泡排序 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } // 输出排序后的结果 for (int num : arr) { System.out.print(num + " "); } } } 这个示例程序使用了冒泡排序算法对一个整数数组进行排序。冒泡排序的基本思想是,重复地比较相邻的元素,如果它们的顺序不对就交换它们的位置,直到整个数组都被排序。在示例程序中,我们使用了两个嵌套的循环来实现这个算法。外层循环控制排序的轮数,内层循环执行每一轮的比较和交换操作。 请注意,在这个示例程序中,我们只是简单地输出了排序后的结果,而没有做任何的错误处理或异常处理。在实际开发中,为了保证程序的健壮性和可靠性,你需要添加适当的异常处理和错误检查代码。 ### 回答2: 堆排序是一种选择排序算法,在数组中建立一个二叉堆,然后反复执行删除最大元素的操作,将被删除的最大元素依次存放在数组的末尾,直到堆为空。以下是一个用Java实现的堆排序算法: java public class HeapSort { public void sort(int arr[]) { int n = arr.length; // 将数组构建成最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 依次取出最大元素并放到数组末尾 for (int i = n - 1; i > 0; i--) { // 将当前最大元素(根节点)与数组末尾元素交换 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 重新构建最大堆 heapify(arr, i, 0); } } // 最大堆调整算法 void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大元素为根节点 int left = 2 * i + 1; // 左子节点的索引 int right = 2 * i + 2; // 右子节点的索引 // 如果左子节点大于根节点,则更新最大元素索引 if (left < n && arr[left] > arr[largest]) largest = left; // 如果右子节点大于根节点,则更新最大元素索引 if (right < n && arr[right] > arr[largest]) largest = right; // 如果最大元素的索引不是根节点,则交换根节点和最大元素,并递归调用对子树进行堆调整 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } // 测试 public static void main(String args[]) { int arr[] = {12, 11, 13, 5, 6, 7}; HeapSort heapSort = new HeapSort(); heapSort.sort(arr); System.out.println("排序后的数组:"); for (int i : arr) System.out.print(i + " "); } } 以上是一个简单的堆排序示例,算法的时间复杂度为O(nlogn)。 ### 回答3: 堆排序是一种基于堆数据结构的排序算法。它的基本思想是将待排序的序列构建成一个大根堆,然后依次将堆顶元素与堆的最后一个元素交换,使得最大的元素逐步从堆中移出,再通过调整堆来使得剩余元素重新构成大根堆,然后再次将堆顶元素与堆的最后一个元素交换,重复进行该过程,直到堆为空。 下面是用Java实现堆排序的代码: java public class HeapSort { public void heapSort(int[] arr) { int n = arr.length; // 构建大根堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 交换堆顶元素和最后一个元素,并调整堆 for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } // 调整堆 void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大元素位置 int l = 2 * i + 1; // 左子节点位置 int r = 2 * i + 2; // 右子节点位置 // 与左子节点进行比较 if (l < n && arr[l] > arr[largest]) largest = l; // 与右子节点进行比较 if (r < n && arr[r] > arr[largest]) largest = r; // 如果最大元素位置改变,则进行交换,并继续调整堆 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } // 打印数组 void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } public static void main(String args[]) { int arr[] = {4, 10, 3, 5, 1}; int n = arr.length; HeapSort heapSort = new HeapSort(); heapSort.heapSort(arr); System.out.println("排序后的数组:"); heapSort.printArray(arr); } } 运行该程序,可以得到如下输出: 排序后的数组: 1 3 4 5 10

最新推荐

Python在线考试系统前端-大学毕业设计-基于vue.zip

Python在线考试系统前端-大学毕业设计-基于vue

Python各种图像注意力模块的实现.zip

注意力机制

300161华中数控财务报告资产负债利润现金流量表企业治理结构股票交易研发创新等1391个指标(2007-2022).xlsx

包含1391个指标,其说明文档参考: https://blog.csdn.net/yushibing717/article/details/136115027 数据来源:基于上市公司公告数据整理 数据期间:从具体上市公司上市那一年开始-2022年度的数据,年度数据 包含各上市公司股票的、多年度的上市公司财务报表资产负债表、上市公司财务报表利润表、上市公司财务报表现金流量表间接法、直接法四表合在一个面板里面,方便比较和分析利用 含各个上市公司股票的、多年度的 偿债能力 披露财务指标 比率结构 经营能力 盈利能力 现金流量分析 风险水平 发展能力 每股指标 相对价值指标 股利分配 11类财务指标分析数据合在一个面板里面,方便比较和分析利用 含上市公司公告的公司治理、股权结构、审计、诉讼等数据 包含1391个指标,如: 股票简称 证券ID 注册具体地址 公司办公地址 办公地址邮政编码 董事会秘书 董秘联系电话 董秘传真 董秘电子邮箱 ..... 货币资金 其中:客户资金存款 结算备付金 其中:客户备付金 .........

【路径规划】基于matlab蚁狮算法栅格地图机器人最短路径规划【含Matlab源码 3065期】.mp4

CSDN佛怒唐莲上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

手机wrap网站html5微信圣诞节点灯送礼专题模板

手机wrap网站html5微信圣诞节点灯送礼专题模板本资源系百度网盘分享地址

DAC简介及参考电路PPT学习教案.pptx

DAC简介及参考电路PPT学习教案.pptx

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

OceanBase数据库简介及原理解析

# 1. OceanBase数据库概述 ## 1.1 OceanBase数据库的发展历程 OceanBase数据库是由阿里巴巴集团自主研发的一款分布式关系型数据库系统,起源于阿里集团的业务需求和技术挑战。自2010年开始研发,经过多年的迭代和优化,OceanBase已经成为阿里巴巴集团重要的核心数据库产品之一。在实际的业务场景中,OceanBase已经被广泛应用于金融、电商、物流等各个领域。 ## 1.2 OceanBase数据库的特点和优势 OceanBase数据库具有以下特点和优势: - **分布式架构**:OceanBase采用多副本分布式架构,可以实现高可用和数据容灾。 -

python的pandas读取excel怎么将excel表里的列从1开始而不是0

在 Pandas 中,数据框的列默认从0开始编号,但我们可以通过自定义函数来进行数据列的转换。可以先将读取的数据框列的第一个值设为1,然后对后续列进行递增处理。 以下是示例代码: ```python import pandas as pd # 读取 Excel 文件 df = pd.read_excel('your_excel_file.xlsx') # 定义函数将列从1开始 def reset_column(x): return str(int(x) + 1) # 应用函数到所有列名 df = df.rename(columns=reset_column) # 打印数据框

第三章薪酬水平、薪酬系统的运行与控制.pptx

第三章薪酬水平、薪酬系统的运行与控制.pptx