堆排序：是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。 代码实现：
package problem; import java.util.Arrays; public class TeatHeapSort { public static void adjust(int[] array,int start,int end) { int tmp = array[start]; for(int i = 2*start+1;i<=end;i=2*i+1) {//找到左右孩子的最大值进行交换，i为最大值下标 if(i<end && array[i]<array[i+1]){//i<end保证有右孩子 i++;//最大值的下标 } if(array[i]>tmp){ array[start]=array[i]; start = i; } if(array[i]<tmp){ break; } } array[start] = tmp; } public static void heapsort(int[] array){ for(int i = (array.length-1-1)/2;i>=0;i--){ adjust(array,i,array.length-1); } //最后一个值与根节点交换 int tmp; for(int j = 0;j<array.length-1;j++){ tmp = array[0]; array[0] = array[array.length-1-j]; array[array.length-1-j] = tmp; adjust(array,0,array.length-1-1-j);//只需要调整最大的数，因为其他子数已经是最大根堆了 } } public static void main(String[] args) { int[] array = {12,5,8,3,9,0,1}; heapsort(array); System.out.println(Arrays.toString(array)); } }执行结果：
