知识卡片

普通读书笔记卡 · 5654.d.1.e.2.a.3.b

堆排序把极值留在已排序尾部

理解等级:中级

原地堆排序先建大顶堆,每轮把根的最大值交换到当前有效堆末尾,缩小堆范围,再从根下沉。已经放定的尾部不再参与堆化,逐步得到升序数组。

有效堆长与数组总长必须分开,否则会把已排序元素重新拉回。迭代下沉可用常数辅助空间,整体时间nlogn;根尾远距离交换可能改变同键次序,因此不稳定。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      由于堆的 长度会随着提取最大元素而减小,因此我们需要给sift_down() 函数添加一个长度参数 ,用于指定堆的当 前有效长度。代码如下所示: // === File: heap_sort.go === /* 堆的长度

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[617,727)) - 结论依据:实际heapSort有效长度参数i、原地交换和siftDown完整代码,稳定性表图204已读确认为非稳定。 - 原始内容:由于堆的 长度会随着提取最大元素而减小,因此我们需要给sift_down() 函数添加一个长度参数 ,用于指定堆的当 前有效长度。代码如下所示: // === File: heap_sort.go === /* 堆的长度