算法-堆排序
package com.jiucaiyuan.net.algrithm.sort; /** * <pre> * 堆排序 * 数组表示二叉树[0,1,2,3,4,5,6] 下标i的左子节点是2*i+1 ,右子节点是 2*i+2 , 父节点是 (i-1)/2 * 大根堆:以i为头的整棵树,最大值是i * 小根对:以i为头的整棵树,最小值是i * 优先级队列结构就是堆结构 * 时间复杂度O(N*logN) 空间复杂度O(1) * </pre> * Created by jiucaiyuan on 2022/3/31. */ public class Sort06_HeapSort { /** * 堆排序算法 * * @param arr * @return */ public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { //O(N) heapInsert(arr, i); //O(logN) } //这个过程处理完,arr也成为大根堆 // for (int i = arr.length; i > 0; i--) { // heapify(arr, i, arr.length); // } int heapSize = arr.length; while (heapSize > 0) { //O(N) swap(arr, 0, --heapSize); //O(logN) heapify(arr, 0, heapSize); //O(1) } } /** * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中 * * @param arr * @param index */ public static void heapInsert(int[] arr, int index) { //如果index位置的数比父节点数大 while (arr[index] > arr[(index - 1) / 2]) { //当前数和父节点数交换 swap(arr, index, (index - 1) / 2); //再判断和父节点大小 index = (index - 1) / 2; } } /** * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中 * * @param arr * @param index */ public static void heapify(int[] arr, int index, int heapSize) { int leftChild = 2 * index + 1; //如果节点有子节点 while (leftChild < heapSize) { //选择较大的子节点下标 int bigger = leftChild + 1 < heapSize && arr[leftChild] < arr[leftChild + 1] ? leftChild + 1 : leftChild; //父和较大子节点较大的数的下标给bigger bigger = arr[index] > arr[bigger] ? index : bigger; //如果父就是较大的数,即不用再处理了 if (index == bigger) { return; } //较大的数和当前数交换 swap(arr, index, bigger); //下次继续判断当前数 index = bigger; leftChild = 2 * index + 1; } } /** * @param arr * @param l * @param r */ private static void swap(int[] arr, int l, int r) { int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } public static void main(String[] args) { int[] arr = {12, 5, 3, 7, 3, 8, 4, 3, 2, 2, 6, 8, 6, 0, 9, 5, 3}; heapSort(arr); print(arr); } private static void print(int[] arr) { if (arr == null) { return; } for (int a : arr) { System.out.print(a + "\t"); } System.out.println(); } }
« 算法-堆排序扩展排序几乎有序数组
|
算法-插入法排序»
日历
个人资料
diaba 寻求合作请留言或联系mail: services@jiucaiyuan.net
链接
最新文章
存档
- 2024年10月(1)
- 2024年8月(2)
- 2024年6月(4)
- 2024年5月(1)
- 2023年7月(1)
- 2022年10月(1)
- 2022年8月(1)
- 2022年6月(11)
- 2022年5月(6)
- 2022年4月(33)
- 2022年3月(26)
- 2021年3月(1)
- 2020年9月(2)
- 2018年8月(1)
- 2018年3月(1)
- 2017年3月(3)
- 2017年2月(6)
- 2016年12月(3)
- 2016年11月(2)
- 2016年10月(1)
- 2016年9月(3)
- 2016年8月(4)
- 2016年7月(3)
- 2016年6月(4)
- 2016年5月(7)
- 2016年4月(9)
- 2016年3月(4)
- 2016年2月(5)
- 2016年1月(17)
- 2015年12月(15)
- 2015年11月(12)
- 2015年10月(6)
- 2015年9月(11)
- 2015年8月(8)
分类
热门文章
- SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
- Mac-删除卸载GlobalProtect
- java.lang.SecurityException: JCE cannot authenticate the provider BC
- MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
- Idea之支持lombok编译
标签
最新评论
- logisqykyk
Javassist分析、编辑和创建jav... - xxedgtb
Redis—常见参数配置 - 韭菜园 ... - wdgpjxydo
SpringMVC:Null Model... - rllzzwocp
Mysql存储引擎MyISAM和Inno... - dpkgmbfjh
SpringMVC:Null Model... - tzklbzpj
SpringMVC:Null Model... - bqwrhszmo
MyBatis-Improper inl... - 乐谱吧
good非常好 - diaba
@diaba:应该说是“时间的度量依据”... - diaba
如果速度增加接近光速、等于光速、甚至大于...
最新微语
- 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界
2022-03-21 23:31
- 2022.03.02 23:37:59
2022-03-02 23:38
- 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!
2018-07-18 10:49
- 2018年关键字“走心”
2018-03-19 16:07
- 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!
2017-12-20 10:24
发表评论: