堆排序实现(java实现)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了堆排序实现(java实现)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1585字，纯文字阅读大概需要3分钟。

内容图文

public class SortClass {
    //堆排序
    public void heapSort(int[] nums) {
        //首先要建立一个大根堆或者小根堆
        int length = nums.length;
        for (int i = 0;i < length;i++) {
            insertMaxHeap(nums,i);
        }
        //每次将最大或者最小的值固定，然后将剩下的元素重新构建堆，再去选出最大或者最小的元素
        while (length > 1) {
            //把现在位于堆顶的元素固定到尾部
            swap(nums,0,length-1);
            length--;
            //继续构建
            buildHeap(nums,0,length);
        }
    }
    private void swap(int[] nums,int x,int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
    private void buildHeap(int[] nums,int i,int length) {
//        //从第一个数到length使用插入的方式去调整数组使之满足最大最小根堆
//        for (int i = 0;i < length;i++) {
//            insertMaxHeap(nums,i);
//        }
        //优化：如果目前的结构已经基本上是一个大根堆或者小根堆了，只有刚替换的这个堆顶元素的位置不正确，则没必要重新构建整个结构了，直接每次和两个子节点中较大的交换位置即可
        int l = (i << 1) + 1;
        int r = (i << 1) + 2;
        while (l < length) {
            int maxIndex = i;
            if (nums[maxIndex] < nums[l]) {
                maxIndex = l;
            }
            if (nums[maxIndex] < nums[r] && r < length) {//注意确保右节点也在置换的范围内
                maxIndex = r;
            }
            //如果父节点已经是最大的了，直接返回即可
            if (maxIndex == i) {
                return;
            }
            swap(nums,maxIndex,i);
            i = maxIndex;
            l = (i << 1) + 1;
            r = (i << 1) + 2;
        }
    }
    private void insertMaxHeap(int[] nums,int i) {
        //把当前要插入的节点与之的父节点进行比较，如果比父节点大的话就与之进行交换，直到父节点大于当前节点或者到达顶点
        int parent = (i-1) >> 1;
        while (parent >= 0 && nums[i] > nums[parent]) {
            swap(nums,i,parent);
            i = parent;
            parent = (i-1) >> 1;
        }
    }
}

 

• 点赞 1
• 收藏
• 分享
• • 文章举报

zjg_java 发布了10 篇原创文章 · 获赞 10 · 访问量 6634 私信 关注

内容总结

以上是互联网集市为您收集整理的堆排序实现(java实现)全部内容，希望文章能够帮你解决堆排序实现(java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---