Question

堆排序是原地排序吗

Answer 1

堆排序是原地排序。

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。

堆排序

堆是一种叫做完全二叉树的数据结构，可以分为大根堆，小根堆，而堆排序就是基于这种结构而产生的一种程序算法。利用堆这种数据结构所设计的一种排序算法，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序的时间复杂度O（N*logN），额外空间复杂度O，是一个不稳定性的排序。