堆排序
这里的堆指的是完全二叉树。
我们先来了解一下大根堆与小根堆。大根堆就是二叉树中所有的父节点都大于子节点，小根堆是二叉树中所有子节点都大于父节点。
数列从小到大排列需要使用大根堆，从大到小需要小根堆
首先我们先看一组数列
现在我们将它先组成一个完全二叉树
--------》将这个完全二叉树变为一个大根堆
最后将第一个数与最后一个交换
这是第一次调整
后面每次进行一次大的调整（第一个数的调整）就可以实现排序了
/* * 堆排序 */ public class Test9 { 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){ //找到 左右孩子的最大值进行交换 if(i < end && array[i] < array[i+1]){//(左孩子小于右孩子) 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 = 0; 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={4,3,5,6,234,56,2}; heapSort(array); System.out.println(Arrays.toString(array)); } }