栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

堆排序(重要)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

堆排序(重要)

堆,又被命名为优先队列。

//时间复杂度:O(nlogn)
//空间复杂度:O(1)
//升序用大顶堆,降序用小顶堆

堆升序排序的思想就是先将待排序的序列建成大根堆,使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素,我们将其与末尾元素交换,使末尾元素为最大值,然后再调整堆顶元素使得剩下的 n-1n−1 个元素仍为大根堆,再重复执行以上操作我们即能得到一个有序的序列。

代码如下:

package 排序_重要.选择排序;
//时间复杂度:O(nlogn)
//空间复杂度:O(1)
//升序用大顶堆,降序用小顶堆
public class 堆排序 {

    public static void main(String[] args) {
        int[] nums = {4,6,8,5,9};
        sortArray(nums);//堆排序
        for (int i : nums){
            System.out.print(i + " ");
        }
    }

    public static int[] sortArray(int[] nums) {
        int last = nums.length-1;//last编号为len-1

        // 将数组整理成大根堆
        heapify(nums);//{9,6,8,5,4}

        // 循环不变量:区间 [0, i] 堆有序
        for (int i = last; i >= 1; ) {
            // 把堆顶元素(当前最大)交换到数组末尾
            swap(nums, 0, i);
            // 逐步减少堆有序的部分
            i--;
            // 下标 0 位置下沉操作,使得区间 [0, i] 堆有序
            siftDown(nums, 0, i);
        }
        return nums;
    }

    
    private static void heapify(int[] nums) {
        int last = nums.length-1;//last编号为len-1
        // 只需要从 i = (last) / 2 这个位置开始逐层下移
        for (int i = last / 2; i >= 0; i--) {
            siftDown(nums, i, last);
        }
    }

    
    private static void siftDown(int[] nums, int i, int last) {
        while (2 * i + 1 <= last) {
            int j = 2 * i + 1;
            if (j + 1 <= last && nums[j + 1] > nums[j]) {
                j++;
            }

            if (nums[j] > nums[i]) {
                swap(nums, j, i);
            } else {
                break;
            }
            i = j;//继续向下遍历
        }
    }

    //交换函数,掌握
    private static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/957255.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号