public class SevenSort {public static void main(String[] args) {int[] arr = new int[] {1,5,3,2,4,10,7,9,8,30,25,26,21,15};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    // 传入任意整形数组arr，对其进行原地堆排序
    public static void heapSort(int[] arr) {// 1.heapify
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {siftDown(arr,i,arr.length);
        }
        // 2.不断交换堆顶元素和数组的最后一个位置
        for (int i = arr.length - 1; i >0; i--) {swap(arr,0,i);
            // 交换之后，大值已经放在了最终的位置
            siftDown(arr,0,i);
        }
    }
    //在arr数组的索引为k的位置进行siftDown操作
    //size有效元素的个数，size的位置是下一个元素插入的位置
   //此时length 相当于size
    
    private static void siftDown(int[] arr, int k, int length) {// 还存在左子树
        while (2 * k + 1< length) {int j = 2 * k + 1;
            if (j + 1< length && arr[j + 1] >arr[j]) {j = j + 1;
            }
            // j就保存了此时左右子树的大值
            if (arr[k] >= arr[j]) {break;
            }else {swap(arr,k,j);
                k = j;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

创新互联是专业的滨湖网站建设公司，滨湖接单;提供做网站、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行滨湖网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：七大排序----SevenSort（堆排序）-创新互联
本文链接：http://ybzwz.com/article/hhpdg.html