【你问我答】快速排序为什么比堆排序快?

问题描述:

快速排序为什么比堆排序快?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!
▶回答尽量有自己的思考,不要单纯的只是复制粘贴定理定义,或者他人blog哦~

你问我答问题汇总:点击进入
关注你问我答栏目:点击关注

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个面试中真实遇到的问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!
#悬赏##面试题目##Java##C/C++#
全部评论
因为堆排序下,数据读取的开销变大。在计算机进行运算的时候,数据不一定会从内存读取出来,而是从一种叫cache的存储单位读取。原因是cache相比内存,读取速度非常快,所以cache会把一部分我们经常读取的数据暂时储存起来,以便下一次读取的时候,可以不必跑到内存去读,而是直接在cache里面找。一般认为读取数据遵从两个原则:temporal locality,也就是不久前读取过的一个数据,在之后很可能还会被读取一遍;另一个叫spatial locality,也就是说读取一个数据,在它周围内存地址存储的数据也很有可能被读取到。因此,在读取一个单位的数据(比如1个word)之后,不光单个word会被存入cache,与之内存地址相邻的几个word,都会以一个block为单位存入cache中。另外,cache相比内存小得多,当cache满了之后,会将旧的数据剔除,将新的数据覆盖上去。在进行堆排序的过程中,由于我们要比较一个数组前一半和后一半的数字的大小,而当数组比较长的时候,这前一半和后一半的数据相隔比较远,这就导致了经常在cache里面找不到要读取的数据,需要从内存中读出来,而当cache满了之后,以前读取的数据又要被剔除。简而言之快排和堆排读取arr[i]这个元素的平均时间是不一样的。
点赞 回复
分享
发布于 2020-06-11 10:22

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务