【Java -- 算法】十大排序算法之堆排序

本文介绍了排序算法的 Java 代码实现，所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。

简介

堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能。

算法步骤

1. 创建一个堆H[0…n-1]

2. 把堆首（最大值）和堆尾互换

3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4. 重复步骤2，直到堆的尺寸为1

实例

1. Java 代码

public class Main {
	public static void main(String[] args) {
	    int[] sort ={3,2,1,4,6,5,8,9,10,7} ;
		System.out.println("排序前：");
		printArray(sort);
		heapSort(sort);
		System.out.println("\n排序后：");
		printArray(sort);
	}
	
	public static void printArray(int[] a) {
	    for (int i = 0;i