知识卡片
堆排序把极值留在已排序尾部
原地堆排序先建大顶堆,每轮把根的最大值交换到当前有效堆末尾,缩小堆范围,再从根下沉。已经放定的尾部不再参与堆化,逐步得到升序数组。
有效堆长与数组总长必须分开,否则会把已排序元素重新拉回。迭代下沉可用常数辅助空间,整体时间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 === /* 堆的长度