一种快速、无分支的稳定快速排序/归并排序混合算法,具有高度的自适应性。
简介----- 本文介绍了一种稳定的快速排序/归并排序混合算法,称为流排序。该排序算法是稳定的、自适应的、无分支的,且性能优异。底部提供了可视化和基准测试。
虽然不如 quadsort 使用的自下而上的运行检测那样灵活,但自上而下的分析器工作得很好,因为快速排序明显受益于对更长范围的排序。这种方法使整体适应性更加可靠,因为 fluxsort 无法被欺骗,使其在小的已排序运行中执行效率较低的分区。如果仅发现随机数据,分析器就会跳过,仅使用 n/4 次比较来分析随机数据。将分段从 4 提高到 16 很有挑战性,因为需要考虑寄存器压力和代码大小。
分区是按自上而下的方式进行的,与快速排序类似。Fluxsort 将小于 2024 个元素的分区的近中位数设为 9,而大于此的分区的中位数分别为 32、64、128、256、512 或 1024,这样就将枢轴选择值与分区大小的立方根相近似。所得到的中位数元素将称为枢轴。小于 96 个元素的分区将使用 quadsort 进行排序。
Fluxsort 的立方根中位数选择与传统的伪中位数 (中位数的中位数) 选择不同,它采用了 quadsort 和二分搜索的组合。在获得了分界点后,数组从开始到结束进行解析。等于或小于分界点的元素
暂无开放 Issues，或尚未同步最近议题。