[数据结构与算法]八大排序-----------------堆排序

堆排序：

1.构建大顶堆

如何构建大顶堆 先将数组的每一个值遍历查询看看有没有对应的孩子节点，再判定孩子节点是否左孩子结点大于右孩子结点，如果小于，让左孩子节点++,然后交换孩子节点与父节点一直遍历，到最后=0，然后再让其孩子节点为父节点，孩子的孩子节点为孩子节点，对比换的时候比孩子节点笑，这样就构建了一个大堆顶

2.交换对顶元素与最后的值，然后length-1继续往上遍历每次确定一个最大的值。

public static void main(String[] args) {
??????? int[] arr = new int[]{5,7,4,2,0,3,1,6};
??????? for (int p = arr.length-1;p>=0;p--){
??????????? adjust(arr,p,arr.length);
??????? }
??????? //堆顶元素和堆底元素进行互换
??????? for(int i = arr.length-1;i>=0;i--){
??????????? int temp = arr[0];
??????????? arr[0] = arr[i];
??????????? arr[i] = temp;
??????????? adjust(arr,0,i);
??????? }
??????? System.out.println(Arrays.toString(arr));
??? }

??? public static void adjust(int[] arr,int parent,int length) {
??????? int Child = 2 * parent + 1;
???? while(Child<length) {
?? ??? ? int rChild = Child+1;
?? ??? ??? ??? ? if(rChild<length && arr[rChild]>arr[Child]) {
?? ??? ??? ??? ??? ? Child++;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? if(arr[parent]<arr[Child]) {
?? ??? ??? ??? ??? ? int temp = arr[Child];
?? ??? ??? ??? ??? ? arr[Child] = arr[parent];
?? ??? ??? ??? ??? ? arr[parent] = temp;
?? ??? ??? ??? ??? ? parent = Child;
?????????????????? Child = 2 * Child + 1;
????????????? }else {
????????????????? break;
????????????? }
?? ??? ??? ??? ? }
???? }