知识卡片

问题卡 · 5654.c.1.a.2.a.6 · 生成模型:未记录

样本下标中位数不是值中位数

理解等级:中级

本书partition生成三个随机下标r[0..2],接着issort(r,3,sizeof(int),compare_int),再读取a[r[1]*esize]作枢轴。这排序的是下标数值,并未按用户compare比较三个数组元素。

因此它不等于正文所说的“三个随机元素值的中位数”。例如采样下标0、1、2且对应值100、1、50时,代码选下标1的值1,值中位数却是50。此例是直接按代码推导,未执行rand或排序。

若落实样本值中位数策略,应按所指元素的比较结果选代表下标,并处理采样重复与辅助排序失败;不能只因函数里有issort调用就认为样本值已经排序。该源码未检查这一issort返回状态,仍不得据此宣称完整中位数保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      中位数法选取一个分割值。一旦选定分割值,就将k往data的左边移动,直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来,将i往右边移动,直到找到一个大于或等于分割值的元素。这个元素属于右边分区。一旦找到的两个元素处于错误的位置,就交换它们的位置。重复这个过程直到i和k重合。(你可能会问

    参考来源

    - 位置:《算法精解:C语言描述》第12章《快速排序的实现与分析》(spine1342;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1308.html;u210-ch12-007)。 - 结论依据:210文字“中位数法”与02955完整r随机下标、compare_int只解引用int、issort(r,...)和读取r[1]代码实读,保留明确错位而非仅批评随机质量。 - 原始内容:中位数法选取一个分割值。一旦选定分割值,就将k往data的左边移动,直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来,将i往右边移动,直到找到一个大于或等于分割值的元素。这个元素属于右边分区。一旦找到的两个元素处于错误的位置,就交换它们的位置。重复这个过程直到i和k重合。(你可能会问