堆排序的原理是什么？

[问答题]

介绍一下，堆排序的原理是什么？

网易全岗位内推官

堆是一个完全二叉树，如果按照层序遍历结果存储为数组，下标为i且根节点i=0，则满足Key[i]>=Key[2i+1]&&Key[i]>=key[2i+2]的称为大根堆，即根结点大于子结点，堆顶为最大值。堆排序第一步建堆，即将输入序列看作是层序遍历结果，然后按顺序写成完全二叉树的形式。第二步调整堆，即从最后一个非叶结点开始调整，它的数组下标为最后一个数的下标-1之后除以2，保证这个结点比子结点大。然后下标减一继续调整，交换结点之后的孩子结点有可能不满足堆的性质，继续调整直到下标为0，这里有递归和非递归两种方法。堆排序就是根据前边建好的堆先取出根结点和最后一个结点交换，然后对前边len-1个结点进行堆调整，再取出根结点和倒数第二个结点交换，对前边len-2个结点堆调整，以此类推直到所有结点都取出。 heapAdjust函数可看做每次都从当前结点走到叶子节点，数高度为log(n+1)向上取整，所以复杂度可视为O(logn)，简单起见，不必考虑到底是从根节点到达叶结点还是从中间某节点到达叶结点。建堆时调用heapAdjust函数n/2次，排序时调用heapAdjust函数n-1次，得到三种情况下的复杂度都是O(logn)* (n/2)+O(logn)*(n-1)，化简为O(nlogn)。空间复杂度O(1)。是不稳定的排序

发表于 2019-04-08 18:47:23 回复(1)