知识卡片
稳定性保留等键相对顺序
稳定排序要求比较键相等的不同记录,在输出中保持它们原来的先后。例如原序中1A在1B前,排序后键都为1时仍应A在B前;这与相同整数值看起来没有区别是两回事。
稳定性来自实现细节,不是所有归并天然稳定。本书merge在compare(left,right)时取左,否则取右,因此两边键相等时右边先输出;以左边1A、右边1B为例会得到1B、1A,是不稳定的。若采用等键先左的合并规则,才可配合稳定子排序保留原相对次序。
后续计数与基数排序要依赖这一性质,不应把“运行结果相同数值”当已检验记录稳定。此例是代码分支推导,未执行或声称已修复merge。
215明确稳定指等值元素相对先后不变,而非每次运行时间一致、结果数值集合相同,或所有输入都相同成本。具体计数实现的倒序填入在217承接,不能由“计数”名称无条件推出任何写法稳定。
217倒序j=size−1到0,并按counts[v]−1填入/递减,是此版稳定性的具体依据;当前int接口没有携带其他记录字段,但按相同规则扩到记录时需完整搬运记录。
218同高位下要保留先前低位次序,正是逐轮稳定排序的作用;并非较低位排过之后元素位置从此绝不能被较高位整体调整。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 稳定性保留等键相对顺序
- · 计数排序的描述
- · 计数排序的实现与分析
- · 基数排序的描述
原书出处 · 4 处
- · 查看原书依据
比较两个集合中的首元素,判断哪个元素将要放到合并的集合中,然后将它放置进去,接着根据元素来自的集合移动ipos或jpos的位置(见图12-4),依此类推。 图 12-4 合并两个有序集 现在我们来看看在mgsort中如何处理递归(见示例12-5)。在初次调用mgsort时,i设置为0,k设置为siz
- · 查看原书依据
稳定的排序能使具有相同数值的元素有相同的顺序,就像它们在原始集合中表现出来的一样。在某些情况下,这是一个重要的特性,我们将在基数排序中看到这一点。
- · 查看原书依据
当temp更新时每个元素的计数要减1,这样在data中出现不止一次的整数也会在temp出现不止一次,这样保持同步。 图 12-6 利用计数算法排序 计数排序的时间复杂度为O(n+k),其中n为要排序的元素的个数,k为data中最大的整数加1。这是由于计数排序包含三个循环,其中两个的运行时间正比于n,
- · 查看原书依据
必须是稳定的。因为,一旦一个数值通过较低有效位的值进行排序之后,此数据的位置不应该改变,除非通过较高有效位的值进行比较后需要它调整位置。例如,在以上的例子中,整数12和15的十位数都包含1,当对其十位数进行排序时,一个不稳定的排序算法可能不会维持其在个位数排序过程中的顺序。而一个稳定的排序算法可以保