愚蠢的想法:首先将所有不同的项目划分为可以相互比较的组,对各个组进行排序,最后将它们连接起来。我假设某项目与某组的第一个成员具有可比性,那么该项目可与该组的所有成员具有可比性。像这样的东西(python3):
import itertools
def python2sort(x):
it = iter(x)
groups = [[next(it)]]
for item in it:
for group in groups:
try:
item < group[0] # exception if not comparable
group.append(item)
break
except TypeError:
continue
else: # did not break, make new group
groups.append([item])
print(groups) # for debugging
return itertools.chain.from_iterable(sorted(group) for group in groups)
在可悲的情况下,这将是二次运行时间,所有项目都不具有可比性,但是我想唯一确定的方法是检查所有可能的组合。对于试图对一长串无法排序的项(例如复数)进行排序的人,将二次行为视为应受的惩罚。在一些字符串和一些整数混合的更常见情况下,速度应类似于普通排序的速度。快速测试:
In [19]: x = [0, 'one', 2.3, 'four', -5, 1j, 2j, -5.5, 13 , 15.3, 'aa', 'zz']
In [20]: list(python2sort(x))
[[0, 2.3, -5, -5.5, 13, 15.3], ['one', 'four', 'aa', 'zz'], [1j], [2j]]
Out[20]: [-5.5, -5, 0, 2.3, 13, 15.3, 'aa', 'four', 'one', 'zz', 1j, 2j]
这似乎也是一种“稳定的排序”,因为这些组是按照遇到无与伦比的项目的顺序形成的。