【数据结构】堆排序问题及其时间复杂度

    xiaoxiao2022-11-07  15

    【问题描述】:关于排序的问题,我们之前见过冒泡排序,其时间复杂度为O(N^2),效率很低,那有没有高效一点的排序方法?我们就要说到堆排序了,本博客中主要讨论堆排序的实现,以及其时间复杂度分析。

    【解题思路】:我们知道如果一个二叉树满足堆的特性,那么堆顶元素则一定是整个堆中最大或最小的元素(这取决于大堆或小堆),那如果我们需要将一组数据进行升序排序,那么我们将这组元素拿来创建一个大堆,堆顶元素为整个数组中最大元素。然后利用堆删除的思想,将堆中最后一个节点的元素与堆顶元素进行交换,现在我们就将这个最大的元素放到了最后一个节点的位置上,接下来将新置换过去的堆顶元素调整至合适位置,再将堆中有效节点个数减一,现在堆顶元素就是整个数组中次大的那个了,同理进行接下来的步骤,最终我们就会得到一个按升序排好序的堆了。

    接下来以升序排序为例,来看一下具体的代码实现:

    堆调整(大堆):

    void Swap(HPDatatype* pLeft, HPDatatype* pRight) { HPDatatype tmp = *pLeft; *pLeft = *pRight; *pRight = tmp; } void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size&&array[child + 1] > array[child]) child += 1; if (array[parent] < array[child]) { Swap(&array[parent], &array[child]); parent = child; child = parent * 2 + 1; } } }

    堆排序:

    void HeapSort(int* array, int size) { //大堆--->升序 //小堆--->降序 int root = ((size - 2) >> 1);//找倒数第一个非叶节点 for (; root >= 0; --root) HeapAdjust(array, size, root); //排序,采用堆删除的思想 int end = size - 1; while (end) { Swap(&array[end], &array[0]); HeapAdjust(array, end, 0); end--; } }

    如果是要降序排序的话,则在堆调整时取小的节点。

    时间复杂度分析:

    先看一下创建堆的时间复杂度:

    需要调整的节点个数:N/2个。根据二叉树的性质我们可知终端节点数n0=度为2节点数n2+1,将常数1忽略掉可得:n0=n2。所有的n2都需要调整,所以需要调整的节点个数为总节点数N/2。

    调整一次的时间复杂度:logN。完全二叉树共有N个节点,高度为log(N+1),化简到logN,调整一次的时间复杂度最差情况需要调整二叉树的高度次,所以调整一次的时间复杂度为logN。

    所以创建堆的时间复杂度为:N/2logN,化简到NlogN。

    然后再来看一下排序时的时间复杂度:排序时我们采用的是删除堆的思想,而删除堆的时间复杂度也是NlogN。

    所以堆排序的时间复杂度为:2NlogN,化简到NlogN。

     

    最新回复(0)