栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【堆排序】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【堆排序】

  • 首先构建一个大顶堆(升序),或者小顶堆(降序)。
  • 将堆顶的元素放到数组的最后位置。
  • 重新调整堆,保证是大顶堆或者小顶堆。
  • 重复上面的操作。
import java.util.Arrays;

public class HeapSort {


	public static void main(String[] args) {
		int[] arr = new int[]{1,2,3,9,8,5,3,2,4};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	private static void heapSort(int[] arr) {
		int len = arr.length;
		// 1.建一个堆。
		buildHeap(arr,len);
		
		for(int i=len-1;i>0;i--){
			//2. 将堆顶和堆尾的元素交换
			swap(arr,0,i);
			len--; // 关键点:放完一次长度减一。
			//3.重调整堆
			heapify(arr,0,len);
		}
	}
	//构造一个堆,
	//从第一个非叶子节点开始
	public static void buildHeap(int[] arr ,int len){
		for(int i=(len/2)-1;i>=0;i--){
			heapify(arr,i,len);
		}
	}
	public static void heapify(int[] arr ,int i ,int len){
		int left = i*2+1;
		int right = i*2+2;
		int biggest = i;
		// 找到最大的那个
		if(leftarr[biggest]){
			biggest=left;
		}
		if(rightarr[biggest]){
			biggest=right;
		}
		//不是 i(最大值不在堆顶) 交换到堆顶位置。
		if(biggest!=i){
			swap(arr,biggest,i);
			heapify(arr,biggest,len);
		}
	}



	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936451.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号