package sort;//最大堆的特性是，某个节点的值最多和其父节点的值一样大。这样，堆中的最大元素存放在根节点中//；并且，在以某一个节点为根的子树中，各节点的值都不大于该子树根节点的值public class HeapSort {       public static void heapSort(int[] list) {          if (list == null || list.length <= 1) {              return;          }        //构建最大堆        //相当于add的作用，此方法结束后，就构建好了有序的二叉堆        buildMaxHeap(list);       //循环，每次把根节点和最后一个节点调换位置        for (int i = list.length - 1; i >= 1; i--) {          	 int tmp = list[0];               list[0] = list[i];               list[i] = tmp;       //每次堆得长度都减少1，也就是排除置换到最后的根节点             //相当于删除最大节点（其实是放在数组最后，然后再排序忽视最后的那些位置）             //把最后的节点放在根节点处，然后在用maxHeap进行比较交换即可             //此时从index=0即交换后的根节点位置开始重新排序             maxHeap(list, 0, i);          }      }      //根据输入数组构建一个最大堆    private static void buildMaxHeap(int[] list) {          if (list == null || list.length <= 1) {              return;          }          //这个half为可能存在子节点的最大的位置        for (int i = list.length/2; i >= 0; i--) {              maxHeap(list, i, list.length);          }      }      //堆调整，使其生成最大堆    private static void maxHeap(int[] list, int index, int heapSize) {         // 左子节点索引    	int left = index * 2 + 1;        //右子节点索引        int right = index * 2 + 2;        //最大节点索引        int largest = index;                 //如果左子节点大于父节点，则将左子节点作为最大节点        if (left < heapSize && list[left] > list[index]) {              largest = left;          }          //如果右子节点比最大节点还大，则最大节点为右子节点        if (right < heapSize &&list[right] > list[largest]) {              largest = right;          }          //最后，如果最大节点和父节点不一致，则交换他们的值        if (index != largest) {          	 int tmp = list[index];               list[index] = list[largest];               list[largest] = tmp;           //交换完父节点和子节点的值，对换了值的子节点检查是否符合最大堆特性            maxHeap(list, largest, heapSize);          }      }              public static void main(String[] args) {          int[] list = { 4,9,8,2,-1,5 };          heapSort(list);          for(int i =0;i<list.length;i++)        	System.out.print(list[i]+" ");    }  }