vlambda博客
学习文章列表

我终于弄懂选择排序(堆排序)

点击蓝字

关注不迷途


选择排序,遍历未排序范围,将最大的元素交换到末尾。


我终于弄懂选择排序(堆排序)


我终于弄懂选择排序(堆排序)


选择排序的最坏、最好、平均时间复杂度都是O(n),空间复杂度是O(1)。


选择排序非常粗暴简单,每次遍历都找到最大的一个数,并将其移到末尾。


那么如何优化选择排序呢?


可以优化的点在于找到最大元素这一步上,可以通过大顶堆来快速找到最大值。


大顶堆的根节点是最大值,小顶堆的根节点是最小值。


对于选择排序的优化,其实就是所谓的堆排序。


先对待排序元素进行大顶堆的构建。


然后交换第一个元素(根节点)与待排序范围的最后一个元素。此时,最大值已经落到末尾。


然后再对末尾前的数组范围元素进行大顶堆的调整。


继续交换最大值直到遍历完数组。


堆排序中构建堆的过程使用siftDown来进行。


我终于弄懂选择排序(堆排序)


从最后一个非叶子节点开始进行构建,最后一个非叶子节点的索引是n/2-1。


siftDown过程是先找出最大子节点,再与当前节点进行比较,如果子节点大,交换节点值,并定位到子节点中进行调整。


我终于弄懂选择排序(堆排序)


构建大顶堆的过程如下


我终于弄懂选择排序(堆排序)


我终于弄懂选择排序(堆排序)


先从最后一个非叶子节点开始进行shifDown,发现左子节点比该节点大,交换左子节点和该节点的值。


然后定位到左子节点的位置上,发现不是非叶子节点,结束。


然后继续上一个索引的节点的siftDown,此时到达节点12的位置。


我终于弄懂选择排序(堆排序)


节点值12比左子节点小,交换两节点值,并定位到左子节点的位置,发现也不是非叶子节点,结束该该轮siftDown。


然后到了根节点的siftDown了。


我终于弄懂选择排序(堆排序)


根节点比最大的子节点小,最大子节点是右子节点24的位置,交换根节点和它的右子节点的值,再定位到右子节点上,发现右子节点是非叶子节点,继续进行siftDown。


到右子节点21的位置,发现比其子节点都大,结束该siftDown操作。


然后发现根子节点都已经完成了siftDown,那么此时大顶堆的构建工作完成了,我们也可以看到根节点24是最大的。


构建完大顶堆后,我们完成了找到一组元素中最大值的任务,最大值就是根节点。


然后再把最大值移到堆的末尾位置。


我终于弄懂选择排序(堆排序)


此时只需要构建剩余的元素。


当然此时不用从最后一个非叶子节点开始进行siftDown,因为只是对根节点进行替换,所以只需要对根节点进行siftDown就可以完成新大顶堆的构建了。


然后再将堆顶元素替换到新堆的末尾。


如此反复,直到剩余一个元素。


此时堆排序完成。


我终于弄懂选择排序(堆排序)


堆排序比选择排序的时间复杂度要好,为O(nlogn),构建大堆顶的时间复杂度为O(n) , 循环替换最大元素并重构建大顶堆的过程时间复杂度为O(nlogn)。


空间复杂度为O(1)。


使用堆排可以解决TopK等问题。


往期推荐



不迷途

我终于弄懂选择排序(堆排序)

关注不迷途

您的关注,是对我最大的认可


喜欢本篇内容顺便点个在看吧