堆排序时间复杂度_堆排序算法

堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。

堆排序基本思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。

堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大根堆；每个节点的值都小于或等于其左右孩子节点的值，称为小根堆。堆排序的最坏时间复杂度为O(n*log2n)，平均时间复杂度为O(n*log2n)。

堆排序算法复杂度

对N个元素建堆的时间复杂度为O(N)，删除堆顶元素的时间复杂度为O(logN)，尽管随着元素的不断删除，堆的调度越来越小，但是总的而言，删除堆所有元素的时间复杂度为O(NlogN)。故堆排序的时间复杂度为O(NlogN)，空间复杂度为O(1)。

对于堆排序而言，数据的初始顺序对它的复杂度没有影响。不管数组初始时就是有序的还是逆序的，它都会先建堆，变成了堆序的性质。从这点上分析，堆排序是一个非常稳定的算法，最坏和平均情况下的时间复杂度都为O(NlogN)。

堆排序的步骤

大根堆有一个很好的性质，根节点的数值总是大于其他所有节点的数值，利用大根堆的这个性质，可以实现排序的工作。步骤如下：

1、构建大根堆。首先我们的原始数组一般情况下是不满足堆的条件，既然我们要可用大根段的性质进行排序，第一步当然是对原始数组进行处理，构建大根堆。

2、根节点数据处理以及大根堆重构。构建大根堆元素之后，根节点的元素是最大值。然后将该数值取出，对剩下的元素进行重构大根堆，这时根节点是剩下元素的最大值，取出。只要不断重复上述的操作，不断取出未排序元素的最大值，直到未排序的元素只剩一个，就完成了排序工作。

堆排序算法分析

堆排序的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。

在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为log2i＋1)，并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度。

再简单总结下堆排序的基本思路：

A、将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

B、将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

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

最后

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，元素需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。