AnT*_*AnT 6 sorting algorithm in-place stable-sort
考虑以下问题.
我们给出了一组属于两个类的元素:红色或蓝色.我们必须重新排列数组的元素,以便所有蓝色元素首先出现(并且所有红色元素都会出现).必须以稳定的方式完成重新排列,这意味着必须保留蓝色元素的相对顺序(红色元素的相对顺序).
是否有一个聪明的算法可以就地执行上述重新排列？
当然,非现场解决方案很简单.
一个明显的就地解决方案是将任何稳定的排序算法应用于阵列.然而,在阵列上使用完整的排序算法直观地感觉就像是一种过度杀伤,特别是考虑到我们只处理两类元素这一事实.
任何想法都非常感激.
小智 6
显然可以在O(n)时间和O(1)空间中进行.该论文由Jyrki Katajainen和Tomi Pasanen声称能够做到这一点,在线性时间内保持最小的空间分割.
谷歌稳定0-1排序.