目录
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.堆排序是选择排序的升级版，但它是一种不稳定的算法。
往期回顾：