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

堆排序详解

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

堆排序详解

1、堆排序首先满足堆的定义,完全二叉树(倒数第二层及以上填满元素)

2、以升序为例,堆化为大顶堆

3、堆化程序

public static void heapify(int[] arr, int i, int length){

        int temp = arr[i];

        //记录开始比较元素的数值

        for(int k = 2 * i + 1; k < length; k = 2 * k + 1){

        // 2i+1是比较元素的左子节点

        // k

        // 2k+1是左子节点的左子节点,(越接近堆顶的堆化,越可能涉及比较子节点的子节点的大小,即用上2k+1的循环,第一次排序前,进行整棵树的堆化,由下→上,由右→左进行堆化)(这个顺序是根据数组索引来的)如图1,

图1 第一次排序前堆化顺序

         if(k + 1 < length && arr[k] < arr[k + 1] ){

                        // 保证不越界的情况下,进行左子节点与右子节点的比较,找出较大的值

                        k++;

                        // 若满足,即右子节点大,将k++,取到右子节点索引

                }

                if(arr[k] > temp){

                // 比较左、右子节点中较大的与temp的关系

                arr[i] = arr[k];

                // 若子节点数值大,则将待比较的初始位置元素替换为子节点数值

                i = k;

                // 未进行arr[k] = temp 原因,多次比较的话,若大一次就替换一次,会有较多的替换操作,i = k 直接定位到较大元素的索引,之后迭代,将最初始的temp,与子树下的节点比较,中间若有需要替换也可根据索引arr[i] = arr[k]进行替换了,因为第二次以及之后的比较前有i = k。 

                } else{

                        break;

                        // 若左、右子节点数值不如temp大,则不用比较啦,退出。原因:第一次排序前,进行整棵树的堆化,由下→上,由右→左进行堆化,见图1

                }

        }

        //for循环结束后,即各个需要比较的子节点均与temp进行比较,最后一个大于temp的元素索引k赋值给了i,i=k,将temp值赋给它。

        arr[i] = temp;

}

//交换数组元素

public static void swap(int[] arr, int a, int b){

        int temp = arr[a];

        arr[a] = arr[b];

        arr[b] = temp;

        }

//排序部分

public static void heapSort(int[] arr){

        for(int i = (arr.length - 1 - 1) / 2 ; i >= 0; i--){

        // 第一次排序前的堆化起始索引: arr.length - 1 - 1 /2

        // i>=0 是由下→上,由右→左进行堆化,到达堆顶,对应数组索引为0

                        heapify(arr,i,arr.length);

                }

        //堆化完进行堆顶和堆尾元素交换(索引分别为0和arr.length - 1),之后再进行堆化交换,第一次排序后的堆化只有堆顶无序,其他的元素都按照之前的堆化排列完毕,所以heapify(int[] arr,int i,int length)中开始堆化的索引i=0,长度length也是每次递减,所以需要使用循环变量作为参数

        for(int j = arr.length - 1; j > 0; j--){

                swap(arr,0,j);

                heapify(arr,0,j);

        }   

}

****----------------程序----------------****

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9,14,10,11,12};
        System.out.println("堆排序前:");
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println("堆排序后:");
        System.out.println(Arrays.toString(arr));
    }

    public static void heapify(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void heapSort(int[] arr) {
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j > 0; j--){
            swap(arr,0,j);
            heapify(arr,0,j);
        }
    }
}

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

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

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