龙空技术网

十大经典排序算法——堆排序

林染lr 116

前言:

此时兄弟们对“算法关于堆的算法”大致比较注意,兄弟们都需要分析一些“算法关于堆的算法”的相关知识。那么小编在网络上收集了一些有关“算法关于堆的算法””的相关内容,希望各位老铁们能喜欢,同学们快快来学习一下吧!

目录

1.1、排序分类

1.2、排序的定义

1.3、术语说明

1.4、算法总结

1.5、图片名词解释

1.6、比较类排序与非比较类排序的区别

2.堆排序(Heap Sort)

2.1、说明

2.2、算法描述

2.3、普通类代码

2.4、推导过程

2.5、以多态、泛型编程和STL实现堆排序

2.6、总结

1.1、排序分类

1.2、排序的定义:

对一序列对象根据某个关键字进行排序。

1.3、术语说明

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。

内排序:所有排序操作都在内存中完成。

外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行。

时间复杂度:一个算法执行所耗费的时间。

空间复杂度:运行完一个程序所需内存的大小。

1.4、算法总结

1.5、图片名词解释:

n: 数据规模。k: “桶”的个数。In-place: 占用常数内存,不占用额外内存。Out-place: 占用额外内存。

1.6、比较类和非比较类的区别

(1)比较类:

1、比较类排序,通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

2、比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。

(2)非比较类排序:

1、不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

2、非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

2.堆排序(Heap Sort)

2.1、说明:

堆排序(Heap sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

最大堆(大顶堆):每个根结点的值都大于或等于其左右孩子结点的值,称为最大堆(大顶堆)。

最大堆(小顶堆):每个根结点的值都小于或等于其左右孩子结点的值,称为最小堆(小顶堆)。

堆的访问:

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

父节点"i"的左子节点在(2i+1)的位置;父节点"i"的右子节点在(2i+2)的位置;子节点"i"的父节点在(i-1)/2的位置;

堆的操作:

①最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点。

②创建最大堆(Build Max Heap):将堆中的所有数据重新排序。

③堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算。

2.2、算法描述

在堆的数据结构中,堆中的最大值总是位于根节点。

它的工作原理:

①将无序序列构建成一个最大堆;

②将堆顶元素与末尾元素交换,将最大元素放到数组的末端;

③重新调整结构,使其满足最大堆的定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

*注:优先队列一般使用最小堆。

2.3、普通类代码(java):2.4、推导过程:

视频加载中...

2.5、以多态、泛型编程和STL实现堆排序(c++)2.6、总结

(1) 分析时间复杂度:

1.它的运行时间是由构建初始堆+交换堆顶元素和末尾元素并重建堆两个部分。其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中,需交换n-1次。

2.无论它最好、最坏和平均时间复杂度均为O(nlogn)。推排序的性能远远好过于冒泡排序、选择排序、插入排序的时间复杂度。

3.堆排序是选择排序的升级版,但它是一种不稳定的算法。

往期回顾:

十大经典排序算法——冒泡排序

十大经典排序算法——选择排序

十大经典排序算法——插入排序

十大经典排序算法——希尔排序

十大经典排序算法——归并排序

标签: #算法关于堆的算法