堆排序优点是什么?堆排序缺点又是什么?

KLQ 2020-06-10 15:11:35 java常见问答 8113

下面的文章内容要给大家讲的就是堆排序的优点和缺点,那么你对于堆排序都了解多少呢?堆排序的优点和缺点是什么?下面就一起来看看详细的介绍吧。

一、堆排序的优点是什么?

首先我们来讲一下堆排序的优点,总的来说,堆排序有以下的几个优点:

1、堆排序效率相对的来说是比较的稳定的,不像快排,在最不好的情况之下,时间复杂度会变成O(n^2))。

所以,不管是待排序序列是不是有序,堆排序的效率都是O(nlogn)保持不变。

同时要注意了,这里的稳定指的是平均时间复杂度=最坏时间复杂度,并不是那个稳定,这是因为,堆排序自身是不稳定的。

2、堆排序的效率和快排、归并一样,都达到了基于比较的排序算法效率的峰值。

3、除了高效以外,最突出的一点就是只要O(1)的辅助空间,它效率高,同时也最节省空间。

堆排序的优点你都了解了吧!那么下面就一起来了解一下堆排序的缺点吧!

二、堆排序的缺点是什么?

从堆排序的优点来看的话,堆排序基本上可以说是完美了,可是,就算是这样,堆排序也是存在着缺点的。

堆排序最大的缺点就是堆的维护问题。

实际场景当中,数据是狠频繁的在发生变化的,而对于待排序序列的每次更新,都需要我们去重新做一遍堆的维护,这样保证它的特性,可是,这在大多数的情况之下,似乎都是没什么必要的。

也正式因为这个,所以说,快排就基本上成为了实际应用当中的老大了,而堆排序,就只能够在算法书里面顶着光环。

当然,在数据更新十分不频繁的时候,用到堆排序还是要好一些的。

延伸阅读:

三、堆排序步骤

下面来给大家讲一下堆排序步骤:

1、构造初始堆

也就是依据待排序序列构造第一个大根堆或者是小根堆

2、首尾交换,断尾重构

也就是对断尾后剩余部分重新构造大(小)根堆

3、将第二步进行重复,一直到首尾重叠,排序完成

好了以上就是对于堆排序优点和缺点的一个介绍了,你都清楚了吧。

更多关于堆排序的相关内容,可以继续通过本站的常见问题栏目来进行了解哦,更多知识可以分享给你。

推荐阅读:

java堆排序代码,堆排序实现

java栈和堆的区别是什么?java对于堆和栈的理解

java栈的特点是什么?java的堆和栈的优缺点介绍