Blitsort 是一种原地稳定的自适应旋转归并排序/快速排序算法。
Blitsort 是一种基于稳定的非原地合并排序 quadsort、稳定的非原地快速排序 fluxsort 和不稳定的原地排序 crumsort 的原地旋转快速/合并排序。本页面主要关注 blitsort 的原地稳定方面,quadsort 和 fluxsort 分别详细介绍了合并排序和稳定快速排序。
可视化-----------------下面的可视化中,上半部分显示交换内存(32 个元素),下半部分显示主内存(512 个元素)。颜色用于区分不同的操作。分区为浅蓝色和深蓝色,旋转为黄色和紫色。blitsort 可视化仅显示随机数据的排序,有序数据的排序与 quadsort GitHub 页面上的 quadsort 可视化相同。
Blitsort 使用与 fluxsort 相同的分析器。它会扫描分布，以确定其中已排序的部分有多少。完全有序或倒序的分布会立即处理。大部分已排序的分段将使用 rotate quadsort 进行排序，否则将使用 rotate fluxsort 进行排序。
旋转归并排序----------------- 旋转归并排序使用旋转来将两个已排序的数组分割成足够小的部分,以便使用辅助内存进行归并。Blitsort 通过从第一个数组中取出中间元素,使用二分查找在第二个数组中找到所有小于中间元素的元素,并对数组进行旋转来实现此操作。它递归执行此操作,直到分区变得足够小以进行归并。
----------------------- 稳定旋转快速排序使用辅助内存将数组分割成多个段,然后通过递归使用旋转将每个段的左侧和右侧分区移动到合适的位置。在随机数据上,它比旋转归并排序更快,因为不需要二分查找,而且无分支优化略有改进。
暂无开放 Issues，或尚未同步最近议题。