为什么堆排序的时间复杂度是O(N*logN)?

这篇具有很好参考价值的文章主要介绍了为什么堆排序的时间复杂度是O(N*logN)?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

堆排序(以排升序为例)

步骤(用大根堆,倒这排,排升序):

1.先把要排列的数组建立成大根堆

2.堆顶元素(82)和最后一个元素交换(2)

3.无视掉交换后的元素(82),对(2)进行向下调整

翻译成代码

mian方法:

heapSortUp方法:

siftDown方法:

堆排序时间复杂度分析:


前言:

本文章以升序为例进行讲解(实际上两种排列时间复杂度都一样,只是比较方式建立大小堆恰好相反)

文章涉及:

1.向下调整算法

2.建堆的方式及其时间复杂度

3.堆排序步骤和时间复杂度分析

注意:如果1,2点还不了解,建议学习完之后在来学习堆排序,才能明白下边讲的是什么。

这里有小编自己写的链接,详细介绍了堆的创建以及向下/向上调整算法:优先级队列(堆)

堆排序(以排升序为例)

如果是排升序,要建立大根堆,反之亦然。

排降序,建立小堆

为什么?

看完他的原理,就知道了。


以数组array={

4,6, 82, 7, 8, 9, 3, 2

}

为例

步骤(用大根堆,倒这排,排升序):

1.先把要排列的数组建立成大根堆

为什么堆排序的时间复杂度是O(N*logN)?,数据结构

2.堆顶元素(82)和最后一个元素交换(2)

为什么堆排序的时间复杂度是O(N*logN)?,数据结构

3.无视掉交换后的元素(82),对(2)进行向下调整

此时又变成了大根堆(无视已经排好的82):

为什么堆排序的时间复杂度是O(N*logN)?,数据结构

此时的82已经被排号了

其是堆排序的整体思路已经讲完了,接下来就是循环执行2,3点
3和9换位置,然后无视排好的82,9,对3进行向下调整:

为什么堆排序的时间复杂度是O(N*logN)?,数据结构

在向下调整完之后,又是一个大根堆,我们继续,循环这个逻辑,最终的结果就变成了:

为什么堆排序的时间复杂度是O(N*logN)?,数据结构

这时,就是一个升序的数组了。

翻译成代码

mian方法:

public class Test {


    public static void main(String[] args) {

        int[] arr = new int[]{4,6, 82, 7, 8, 9, 3, 2};//要排的数组
        BigHeap bigHeap = new BigHeap();//这个是我自己写的大根堆
        bigHeap.init(arr);//把数组传入对象
        bigHeap.creatHeap();//先建立起大堆
        bigHeap.heapSortUp();//进行堆排序


    }
}

heapSortUp方法:

1.我的堆,底层使用elem的数组实现的!!!!!

2.useSize是堆的容量

3.swap的两个参数都是数组的下标

public int[] heapSortUp() {


        int endIndex = useSize - 1;//最后一个下标的位置(也就是容量减1)
        while (endIndex > 0) {//如果等于零,就不用交换了
            swap(0, endIndex);//顶元素和最后一个元素交换
            endIndex--;//最后一个下标--,就可以起到无视排号数,的作用
            siftDown(0, endIndex);
        }
        return elem;
    }

siftDown方法:

public void siftDown(int parent, int end) {//parent end都是有效下标

        int child = 2 * parent + 1;//默认是左孩子
        while (child <= end) {//调整到最后一个子节点,为止
            //先判断是否有右孩子
            if (child + 1 <= end) {//如果有判断谁大,大的当左孩子
                if (elem[child] < elem[child + 1]) {
                    child++;
                }
            }

            //左孩子在和父节点进行比较
            if (elem[child] > elem[parent]) {//如果孩子节点大,那么父子交换位置
                swap(child, parent);
            } else {
                break;//如果父节点已经是最大的就不用调整了,这棵树就是大根堆
                //因为我们会从后往前,把这棵树(数组)一次遍历调整完
            }
            //下面继续往往下面调整
            parent = child;//当前的父亲,变成自己的孩子
            child = parent * 2 + 1;//孩子变成孩子的孩子
        }
    }

堆排序时间复杂度分析:

其实很简单,上面我们一共说了三个方法:

1.main

2.heapSortUp

3.siftDown

我们从main方法切入,实际上执行堆排序的程序就是这两步:

 public static void main(String[] args) {

        int[] arr = new int[]{4,6, 82, 7, 8, 9, 3, 2};
        BigHeap bigHeap = new BigHeap();
        bigHeap.init(arr);

//这两步:
        bigHeap.creatHeap();//先创建大根堆
        bigHeap.heapSortUp();//堆排序,内部实现等一下看


    }

学了堆我们都直到,建堆的时间复杂度是O(N)

然后在加上heapSortUp的时间复杂度,不就是堆排序的时间复杂度了吗?

具体看一下,heapSortUp:

 public int[] heapSortUp() {


        int endIndex = useSize - 1;
        while (endIndex > 0) {
            swap(0, endIndex);
            endIndex--;
            siftDown(0, endIndex);
        }
        return elem;
    }

useSize和siftDown是我们要计算的时间复杂度,其他都是常量不用管

useSize实际上就是所给数组的长度嘛,就是N咯

学了siftDown就是向下调整算法,向下调整算法向上调整算法的时间复杂度都是logN(以2为底)-----》至于怎么算的,可以看小编文章前言部分的链接

所以堆排序的时间复杂度==O(useSize)+O(siftDown)*O(creatHeap)=N+N*logN

然后取得最高阶,则时间复杂度就是O(N*logN)文章来源地址https://www.toymoban.com/news/detail-857270.html

到了这里,关于为什么堆排序的时间复杂度是O(N*logN)?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 希尔排序及其时间复杂度(图文详解)

    😾 博客主页: 爱吃bug的猿 🚀 博客专栏: 数据结构,C语言初阶进阶全流程讲解 😽😽😽 如果喜欢博主的文章,可以给博主点波赞和关注加速博主更新 希尔排序里的一部分和插入排序极其相似,了解插入排序及其复杂度(动图讲解)可点击此处 希尔排序分为两部分:预排序

    2024年02月13日
    浏览(36)
  • 常见的排序算法的时间复杂度

    排序算法的时间复杂度通常取决于输入数据的规模(通常表示为n)。以下是一些常见排序算法及其平均、最好和最坏情况下的时间复杂度: 1、冒泡排序(Bubble Sort) 平均时间复杂度:O(n^2) 最好情况时间复杂度:O(n) 最坏情况时间复杂度:O(n^2) 冒泡排序通过重复地遍历待排序

    2024年04月13日
    浏览(32)
  • 什么是时间复杂度和空间复杂度

    🍕博客主页:️自信不孤单 🍬文章专栏:数据结构与算法 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏+关注 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法(Algorithm):就是定义良好的计算过程

    2023年04月15日
    浏览(41)
  • 排序算法的时间复杂度存在下界问题

    对于几种常用的排序算法,无论是归并排序、快速排序、以及更加常见的冒泡排序等,这些排序算法的时间复杂度都是大于等于O(n*lg(n))的,而这些排序算法存在一个共同的行为,那就是这些算法在对元素进行排序的时候,都会进行同一个操作,也就是对数组中取出文件,然后

    2024年02月21日
    浏览(41)
  • 常见的排序算法及时间空间复杂度

    排序算法是计算机科学中的基本算法之一,它用于将一组数据按照某种顺序进行排列。下面是一些常见的排序算法,以及它们的思想和时间空间复杂度,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1. 冒泡排序 (Bubble Sort) - 思

    2024年02月07日
    浏览(39)
  • 快速排序算法详解(原理,时间复杂度,实现代码)

    快速排序算法详解(原理、实现和时间复杂度) 快速排序是对冒泡排序的一种改进,由 C.A.R.Hoare(Charles Antony Richard Hoare,东尼·霍尔)在 1962 年提出。 快速排序的基本思想是 :通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据

    2024年02月13日
    浏览(48)
  • 时间复杂度为 O(n) 的排序算法

    大家好,我是 方圆 。本文介绍线性排序,即时间复杂度为 O(n) 的排序算法,包括桶排序,计数排序和基数排序,它们都不是基于比较的排序算法,大家重点关注一下这些算法的适用场景。 桶排序 桶排序是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶

    2024年02月21日
    浏览(41)
  • 时间复杂度为 O(nlogn) 的排序算法

    归并排序 归并排序遵循 分治 的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下: 划分 :分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列,将长数组的排序

    2024年02月07日
    浏览(33)
  • 时间复杂度为 O(n^2) 的排序算法

    大家好,我是 方圆 。对于小规模数据,我们可以选用时间复杂度为 O(n 2 ) 的排序算法,因为时间复杂度并不代表实际代码的执行时间,而且它也省去了低阶、系数和常数,仅代表的增长趋势,所以在小规模数据情况下, O(n 2 ) 的排序算法可能会比 O(nlogn) 的排序算法执行效率

    2024年02月07日
    浏览(46)
  • 时间复杂度接近O(n)的三种排序算法

    桶排序,顾名思义,会用到“桶”,核心思想是将要排序的数据分到几个有 序的桶里,每个桶内的数据再单独进行排序。桶内排完序之后,再把每个桶内的数据按照顺序依次 取出,组成的序列就是有序的了。 桶排序对要排序数据的要求是非常苛刻的。 首先,要排序的数据需

    2024年02月14日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包