请选择 进入手机版 | 继续访问电脑版

石家庄老站长

点击联系客服
客服QQ: 客服微信:
 找回密码
 立即注册
查看: 19|回复: 0

图片茂盛-了解堆排序

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-10-1 07:29:12 | 显示全部楼层 |阅读模式
堆排序基本介绍








堆排序基本思想





堆排序详细图解













=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5aiB5pav5biD6bKB5YWLLueMqeeMqQ==,size_20,color_FFFFFF,t_70,g_se,x_16" width="1052" />






堆排序基本思路的总结:
1)将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

2)将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

3)重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整 + 交换步骤,直到整个序列有序。

代码实现
public class HeapSort {
        public static void main(String[] args) {
                // 要求将数组进行升序排序
                int arr[] = { 4, 6, 8, 5, 9};
                heapSort(arr);
        }
        // 编写一个堆排序的方法
        public static void heapSort(int arr[]) {
                int temp = 0;
                System.out.println("堆排序!!");
                // 1.将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
                for (int i = arr.length / 2 - 1; i >= 0; i--) {
                        adjustHeap(arr, i, arr.length);
                }
                // 2.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
                // 3.重新调整架构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤。
                for (int j = arr.length - 1; j > 0; j--) {
                        // 交换
                        temp = arr[j];
                        arr[j] = arr[0];
                        arr[0] = temp;
                        adjustHeap(arr, 0, j);
                }
                System.out.println("数组=" + Arrays.toString(arr));
        }
        // 将一个数组(二叉树),调整成一个大顶堆
        /**
         * 功能:完成将以i对应的非叶子节点的树调整成大顶堆 举例:int arr[] = {4,6,8,5,9} => i = 1 => adjustHeap =>
         * 得到{4,9,8,5,6} 如果再次调用 addjustHeap 传入的是 i = 0 => 得到{4,9,8,5,6} => {9,6,8,5,4}
         *
         * @param arr    待调整的数组
         * @param i      表示非叶子节点再数组中索引
         * @param length 表示对多少个元素继续调整,length 是在逐渐的减少
         */
        public static void adjustHeap(int arr[], int i, int length) {
                int temp = arr;// 先取出当前元素的值,保存在临时变量
                // 开始调整
                // 说明
                // 1.k = i * 2 + 1 k是i节点的左子节点
                for (int k = i * 2 + 1; k  temp) {// 如果子节点大于右节点
                                arr = arr[k];// 把较大的值赋给当前节点
                                i = k;// !!! i指向k,继续循环比较
                        } else {
                                break;
                        }
                }
                // 当for循环结束后,就已经将以i为父节点的树的最大值,放在了最顶
                arr = temp;// 将temp值放到调整后的位置
        }
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|石家庄@IT精英团

GMT+8, 2021-10-17 22:58 , Processed in 0.187201 second(s), 25 queries .

Powered by Discuz! X3.4

© 2001-2021 Comsenz Inc.

快速回复 返回顶部 返回列表