易语言资源网 - 做最全的易语言资源下载社区
精易论坛授权登录

7.初级例程-挑选第n小-理论上比快速排序快6倍,实际更多   [复制链接]

    2023-10-06 08:59:15
    进阶教程源码
    易语言资源网
    472 次浏览
    来源链接

挑选和排序是相关的。

排序要求将整个数据数组重排,而挑选则只请求选出一个返回值:在 N 个元素中哪一个是第N个小的元素 (或等效地,第m=N+1-k大的元素)?

遗憾的是,为了挑选的计算目的、挑选的最快方法需重整数组,典型的是将所有较小的元素置于第N个元素之左,所有较大元素置于右,并且在每一个子集内顺序是杂乱的。

这种副作用轻者是无害的,重者就十分的不方便。还有一种方法不打乱原数组的顺序。这种定点挑选法比更快的方法慢约 10 倍, 本帖暂时不发。

挑选通常用于对一组数据进行统计定性。通常想知道一列数据的中间值,或上四分之一或下四分之一值。

当N是奇数时,中间值就是第N个元素,其中 k=(N+1)/2。 当N 是偶数时,统计书上定义中间值是 k=N/2和 k=N/2+1 两元素(也就是从上数第 N/2 和从下数第 N/2)的算术平均值。如果接受这种规定,就必须分别进行两次挑选,来找到这些值。对于 N>100,通常定义 k=N/2 为中间元素,不按这种规定。

若允许重排数组,最快的挑选方法则就是“划分法”,与快速排序法中探作完全相同。挑选一个“随机”分割元素,用它来核对整个序列,迫使较小的元素排列左边。较大的排到右边。正如在快速排序法中那样,优化内循环是非常重要的,使用“限制”来减少比较的数量。但在排序中,还需对分割出的两个子数组分别继续进行操作。然而在挑选中,可以略去一个子数组,而只注意包含了要找的第k元素的那一个子集。用划分法来挑选就不需要用于操作期间的堆栈,并且它的运算量是 N 量级而不是 N*log(N) 量级。

对照快速排序算法,下列例程就很容易明白。

image.png



点我下载 (已有 11 次下载)

引用模块


源码文件名 模块文件名
7.挑选第n小.e
精准计时.ec


引用支持库


源码文件名 支持库文件名 支持库标识
7.挑选第n小.e 系统核心支持库 5.7 d09f2340818511d396f6aaf844c7e325
特殊功能支持库 3.1 A512548E76954B6E92C21055517615B0


[错误报告]   上一篇:画圈     下一篇:文件操作模块,支持大文件操作...