网站LOGO
逐暗者的麦田
页面加载中
7月22日
网站LOGO 逐暗者的麦田
一个java软件攻城狮
菜单
  • 逐暗者的麦田
    一个java软件攻城狮
    用户的头像
    首次访问
    上次留言
    累计留言
    我的等级
    我的角色
    打赏二维码
    打赏博主
    排序算法:堆排序
    点击复制本页信息
    微信扫一扫
    文章二维码
    文章图片 文章标题
    创建时间
  • 一 言
    确认删除此评论么? 确认
  • 本弹窗介绍内容来自,本网站不对其中内容负责。
    • 复制图片
    • 复制图片地址
    • 百度识图
    按住ctrl可打开默认菜单

    排序算法:堆排序

    shellingford · 原创 ·
    程序人生 · 算法排序
    共 3439 字 · 约 2 分钟 · 150
    本文最后更新于2024年05月14日,已经过了69天没有更新,若内容或图片失效,请留言反馈

    堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

    1. 堆中某个结点的值总是不大于或不小于其父结点的值;
    2. 堆总是一棵完全二叉树。

    将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

    例如:

    构建堆

    数组和堆的特点

    1. 使用一维数组来表示一个堆,下标从0~n,0表示堆顶
    2. 如果一个节点的下标为x,那么左子节点的下标为 2x+1,右子节点的下标为2x+2
    3. 如果一个节点的下标为x,那么父节点的下标为(x-1)/2

    堆化

    在一个已经是最大堆(或者最小堆)的末尾插入一个数据,有可能会打破这个最大堆(或者最小堆)

    如下图,在一个最大堆末尾插入一个14的数据,就打破了这个最大堆。这时需要进行堆化处理。

    处理方式就是,用这个插入的节点和其父节点对比,如果比父节点大,则互相交换。

    交换后再继续和其父节点比较,直至堆顶。

    构建堆

    由于堆的节点和数组下标有着明显的对应特征,所以构建一个堆只需要固定的几个临时变量,空间复杂度只有O(1)。

    构建一个堆也比较简单:

    1. 首先认为下标0的数据为堆顶
    2. 接着认为向这个最大堆(或者最小堆)的末尾(首次下标是1)插入数据
    3. 处理这个新插入的数,使数据堆化
    4. 重复2~3的步骤,直至数组最后一个元素

    需要注意的是:如果要升序排序,则需要构建最大堆,如果要降序排序,则需要构建最小堆

    排序

    排序步骤也比较简单,就是在执行剔除堆顶的操作

    1. 交换堆顶(下标为0)的数据和数组最后一个(首次下标为n)的数据,此时最后一个数据是已升序排列完的数据
    2. 由于步骤1,导致打破了最大堆(或者最小堆),执行堆化操作
    3. 再重复1~2 直至整个堆只剩下堆顶一个数据为止

    示意图

    时间复杂度和空间复杂度

    堆的构建时间复杂度:O(n2)
    排序时间复杂度:O(nlogn)

    稳定性

    由于对序列跳跃式维护堆的结构性质,相同值顺序无法得到保障,所以堆排序是不稳定的。

    代码

    java 代码:
        public void sort(int[] nums){
            buildHeap(nums);
            int point = nums.length - 1;
            while(point > 0){
                int temp = nums[0];
                nums[0] = nums[point];
                nums[point] = temp;
                heapity(nums,point);
                point--;
            }
        }
    
        private void heapity(int[] nums, int point) {
            int index = 0;
            while(index <= point){
                int left = 2 * index + 1;
                int right = left +1;
                if(left >= point){
                    //超出界限
                    return;
                }else if(right >= point){
                    //右子节点超出边界
                    if(nums[left] > nums[index]){
                        int temp = nums[left];
                        nums[left] = nums[index];
                        nums[index] = temp;
                        index = left;
                    }else{
                        return;
                    }
                }else{
                    if(nums[left] >= nums[right] && nums[left] > nums[index]){
                        int temp = nums[left];
                        nums[left] = nums[index];
                        nums[index] = temp;
                        index = left;
                    }else if(nums[right] >= nums[left] && nums[right] > nums[index]){
                        int temp = nums[right];
                        nums[right] = nums[index];
                        nums[index] = temp;
                        index = right;
                    }else{
                        return;
                    }
                }
            }
        }
    
        private void buildHeap(int[] nums) {
            for (int i = 1; i < nums.length; i++) {
                buildHeap(nums,i);
            }
        }
    
        private void buildHeap(int[] nums,int index) {
            while(index > 0 ) {
                int parentIndex = (index-1) / 2;
                if (nums[parentIndex] < nums[index]) {
                    int temp = nums[parentIndex];
                    nums[parentIndex] = nums[index];
                    nums[index] = temp;
                    index = parentIndex;
                } else {
                    return;
                }
            }
        }
    声明:本文由 shellingford(博主)原创,依据 CC-BY-NC-SA 4.0 许可协议 授权,转载请注明出处。

    还没有人喜爱这篇文章呢

    我要发表评论 我要发表评论
    博客logo 逐暗者的麦田 一个java软件攻城狮
    MOEICP 萌ICP备20237379号 ICP 沪ICP备13037081号-2,沪ICP备13037081号-1,沪ICP备13037081号-3 又拍云 本站由又拍云提供CDN加速/云存储服务

    💻️ shellingford 7月14日 在线

    🕛

    本站已运行 2 年 331 天 7 小时 55 分

    🌳

    自豪地使用 Typecho 建站,并搭配 MyLife 主题
    逐暗者的麦田. © 2021 ~ 2024.
    网站logo

    逐暗者的麦田 一个java软件攻城狮