Java 十大排序算法之堆排序刨析

2024-10-30 05:23:38

二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性︰

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆)。

任意节点的值都大于其子节点的值——大顶堆（最后输出从小到大排）
任意节点的值都小于其子节点的值———小顶堆（最后输出从大到小排）

堆排序步骤

1.堆化，反向调整使得每个子树都是大顶或者小顶堆（建堆）
2.按序输出元素∶把堆顶和最末元素对调，然后调整堆顶元素（排序）

堆排序代码实现（大顶堆）

public class HeapSort {
    private static void heapSort(int[] arr) {
        // 构造初始堆（大顶堆）,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        // 调整堆结构，交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换
            heapAdjust(arr, 0, j);// 重新对堆进行调整
        }
    }

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

    // 调整大顶堆
    private static void heapAdjust(int[] arr, int i, int len) {
        int temp = arr[i], index = 2 * i + 1;
        while (index < len) {
            if (index + 1 < len && arr[index] < arr[index + 1]) {// 如果左子结点小于右子结点，index指向右子结点
                index += 1;
            }
            if (arr[index] > temp) {// 如果子节点大于父节点，将子节点值赋给父节点
                arr[i] = arr[index];
                i = index;
                index = 2 * i + 1;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

时间复杂度：O(nlogN)

到此这篇关于Java 十大排序算法之堆排序刨析的文章就介绍到这了,更多相关Java 堆排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

详解堆排序算法原理及Java版的代码实现

概述堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,
Java堆排序算法详解

堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+
JAVA堆排序算法的讲解

预备知识堆排序堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是: 大顶
图解Java排序算法之堆排序

目录预备知识堆排序堆堆排序基本思想及步骤再简单总结下堆排序的基本思路: 总结预备知识堆排序堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面
Java 归并排序算法、堆排序算法实例详解

基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

本文实例汇总了Java各种排序算法.分享给大家供大家参考,具体如下: 1. 冒泡排序: public class SortTest { public static void main(String[] args) { int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345}; show(a); bubbleSort(a); show(a); } private static void bubbleSo
JAVA十大排序算法之堆排序详解

目录堆排序知识补充二叉树满二叉树完全二叉树二叉堆代码实现时间复杂度算法稳定性思考总结堆排序这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树堆中某个结点的值总是不大于或不小于其父结点的值知识补充二叉树树中节点的子节点不超过2的有序树满二叉树二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有
堆排序算法的讲解及Java版实现

堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆
Java排序算法总结之堆排序

本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏
Java 十大排序算法之堆排序刨析

二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1．父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2．每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ
Java 十大排序算法之冒泡排序刨析

目录冒泡排序原理冒泡排序API设计冒泡排序的代码实现冒泡排序的时间复杂度分析冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值冒泡排序API设计类名 Bubble 构造方法 Bubble:创建Bubble对象成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C
Java 十大排序算法之插入排序刨析

目录插入排序原理插入排序API设计插入排序代码实现插入排序的时间复杂度分析插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位插入排序API设计类名 Insertion 构造方法 Insertion():创建Insertion对象成员方法 1.public static void sort
Java 十大排序算法之归并排序刨析

目录归并排序原理归并排序API设计归并排序代码实现归并排序的时间复杂度分析归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计类名 Merge 构造方法 Merge():创建Merge对象成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行
Java 十大排序算法之选择排序刨析

目录选择排序原理选择排序API设计选择排序代码实现选择排序的时间复杂度选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值选择排序API设计类名 Selection 构造方法 Selection():创建Selection对象成员方法 1.public static void sort(Comparable[] a):对
Java 十大排序算法之希尔排序刨析

目录希尔排序原理希尔排序的API设计希尔排序的代码实现希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计类名 Shell 构造方法 Shell():创建Shell对象成员方法 1.public static void sort(Comparable
Java 十大排序算法之计数排序刨析

计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素计数排序优缺点优点:快缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费使用范围:数据较为密集或范围较小时适用. 思路 1.找出最大元素max 2.初始化一个max+1的数组 3.将每个元素的计数存储在数组中各自的索引处 4.存储计数数组元素的累积和 5.数组中找到原始数组的每个元素的索引计数排序代码实现 public class CountingSort { private static
JAVA十大排序算法之桶排序详解

目录桶排序代码实现时间复杂度算法稳定性总结桶排序桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中. 桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效. 代码实现 1.找出数组中的最大值max和最小值min,可以确定出数组所在范
JAVA十大排序算法之计数排序详解

目录计数排序问题代码实现时间复杂度算法稳定性总结计数排序一种非比较排序.计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法.但计数排序局限性比较大,只限于对整数进行排序,而且待排序元素值分布较连续.跨度小的情况. 如果一个数组里所有元素都是整数,而且都在0-k以内.对于数组里每个元素来说,如果能知道数组里有多少项小于或等于该元素,就能准确地给出该元素在排序后的数组的位置. 如给定一个0~5范围内的数组[2,5,3,0,2,3,0,3],对于元素5为其中最大的元素

Java 十大排序算法之堆排序刨析

堆排序步骤

堆排序代码实现（大顶堆）

相关推荐

随机推荐