7.初级例程-挑选第n小-理论上比快速排序快6倍，实际更多

明天自然醒 · 发表于 2023-9-26 10:15:05

数据量50w
快速排序后挑选第n小
* “耗时：182.6337000001 ms”
* 10.160720
本算法挑选第n小
* “耗时：11.20310000004 ms”
* 10.160720

挑选和排序是相关的。
排序要求将整个数据数组重排，而挑选则只请求选出一个返回值：在 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) 量级。

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

7.挑选第n小.zip (4.55 KB, 下载次数: 69)

SSS777 · 发表于 2024-4-15 09:00:09

学习了，谢谢楼主

lm88818 · 发表于 2024-1-29 09:25:08

支持开源~！感谢分享

想学易语言 · 发表于 2024-1-15 20:08:12

支持开源~！感谢分享

11111390 · 发表于 2023-11-13 16:50:47

感谢大神分享

jonn · 发表于 2023-10-7 04:35:34

下载学习！！

huomu · 发表于 2023-10-5 19:26:41

很好很强悍，坚持下去哦~

财财发大财 · 发表于 2023-10-1 00:05:41

支持开源~！感谢分享

网络注册络员 · 发表于 2023-9-30 17:20:11

感谢分享

柠檬秋刀鱼 · 发表于 2023-9-29 17:22:44

感谢分享

		自动登录	找回密码
密码			注册

[易语言纯源码] 7.初级例程-挑选第n小-理论上比快速排序快6倍，实际更多

评分