排序一个清单：数字升序排列，字母降序

问题描述：

这个问题实际上是从one previously asked by Mat.S（image）改编而来。尽管它被删除了，但我认为这是一个很好的问题，所以我要以更明确的要求和我自己的解决方案来重新发布它。排序一个清单：数字升序排列，字母降序

鉴于字母和数字的清单，说

['a', 2, 'b', 1, 'c', 3]

的需求是在下降，在上升的数字和字母排序，而不改变字母和数字的相对位置。我的意思是，如果未排序列表是：

[L, D, L, L, D] # L -> letter; # D -> digit

然后，排序列表也必须

[L, D, L, L, D]

的字母和数字的规律做不一定替代 - 他们可以以任意顺序出现
排序后 - 数字递增，字母递减。

因此对于输出上面的例子是

['c', 1, 'b', 2, 'a', 3]

又如：

In[]: [5, 'a', 'x', 3, 6, 'b'] 
Out[]: [3, 'x', 'b', 5, 6, 'a']

什么是做到这一点的好办法？

看起来很像一个：https://stackoverflow.com/questions/44685760/how-排序字符串 –

@cᴏʟᴅsᴘᴇᴇᴅ：为了阻止那些不明白本网站鼓励自我回答的人，我过去在我的问题下发表了一条评论：* PS。有些人可能会认为我发布后回答自己的问题是错误的。在downvoting之前，请阅读[可以问和回答你自己的问题]（http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/） * –

@ Jean-FrançoisFabre哈哈依稀记得那一个。是的，它有点类似。猜猜我无意中从那里拿起了另一个诀窍。 –

答

下面是使用defaultdict()和bisect()一个优化的方法：

In [14]: lst = [5, 'a', 'x', 3, 6, 'b'] 
In [15]: from collections import defaultdict  
In [16]: import bisect 

In [17]: def use_dict_with_bisect(lst): 
      d = defaultdict(list) 
      for i in lst: 
       bisect.insort(d[type(i)], i) 
      # since bisect doesn't accept key we need to reverse the sorted integers 
      d[int].sort(reverse=True) 
      return [d[type(i)].pop() for i in lst] 
    .....:

演示：

In [18]: lst 
Out[18]: [5, 'a', 'x', 3, 6, 'b'] 

In [19]: use_dict_with_bisect(lst) 
Out[19]: [3, 'x', 'b', 5, 6, 'a']

如果你正在处理较大列表它更优化的使用bisect具有约0复杂度（N ）下降，只是使用Python内置sort()功能与NLOG（n）的复杂性。

In [26]: def use_dict(lst): 
      d = defaultdict(list) 
      for i in lst: 
       d[type(i)].append(i) 
      d[int].sort(reverse=True); d[str].sort() 
      return [d[type(i)].pop() for i in lst]

与其他答案基准测试出使用dict和内置sort几乎1ms的快比其他方法方面的最新方法：

In [29]: def use_sorted1(lst): 
       letters = sorted(let for let in lst if isinstance(let,str)) 
       numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
       return [letters.pop() if isinstance(elt,str) else numbers.pop() for elt in lst] 
    .....: 

In [31]: def use_sorted2(lst): 
       f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 
       f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 
       return [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
    .....: 

In [32]: %timeit use_sorted1(lst * 1000) 
100 loops, best of 3: 3.05 ms per loop 

In [33]: %timeit use_sorted2(lst * 1000) 
100 loops, best of 3: 3.63 ms per loop 

In [34]: %timeit use_dict(lst * 1000) # <-- WINNER 
100 loops, best of 3: 2.15 ms per loop

这里是一个基准，显示了使用bisect如何可以减慢长列表的处理过程：

In [37]: %timeit use_dict_with_bisect(lst * 1000) 
100 loops, best of 3: 4.46 ms per loop

每当我看到'bisect'时我用_have_来upvote） –

声称插入排序是一种“优化方法”，虽然用二进制搜索来找到插入点，但有点过分。很显然，对于小型输入来说很好。 –

@SteveJessop当然，实际上使用平分并不是我称之为优化的唯一原因。这是因为它与字典相结合。否则，创建列表并使用使用Tim Sort算法的“sorted”（具有“Nlog（N）”顺序）对于较长的列表稍快。 – Kasramvd

答

看，不用iter：

lst = ['a', 2, 'b', 1, 'c', 3] 
letters = sorted(let for let in lst if isinstance(let,str)) 
numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
lst = [(letters if isinstance(elt,str) else numbers).pop()for elt in lst]

我正在寻找一种方式把它变成一个（恐怖）的单行，但至今没有运气 - 建议表示欢迎！

答

我把在此裂纹通过创建两个发电机，然后从他们服用有条件：

In [116]: f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 

In [117]: f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 

In [118]: [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
Out[118]: ['c', 1, 'b', 2, 'a', 3]

答

在一个行：

list(map(list, sorted(zip(lst[::2], lst[1::2]), key=lambda x: x[1] if hasattr(x[0], '__iter__') else x[0])))

答

要理论上不推荐，但我很乐意编码它。

from collections import deque 
from operator import itemgetter 

lst = ['a', 2, 'b', 1, 'c', 3] 
is_str = [isinstance(e, str) for e in lst] 
two_heads = deque(map(itemgetter(1), sorted(zip(is_str, lst)))) 
[two_heads.pop() if a_str else two_heads.popleft() for a_str in is_str]

答

为什么我们不按升序排序列表，但要确保号码前加字母来：

[D, D, L, L, L] # L -> letter; # D -> digit

我们可以做到这一点以这样的方式：

>>> lst = [5, 'a', 'x', 3, 6, 'b'] 
>>> sorted(lst, key=lambda el: (isinstance(el, str), el)) 
[3, 5, 6, 'a', 'b', 'x']

然后我们从左到右查看原始数组，如果遇到数字，我们会从排序数组的开始处选择元素，否则从结尾处开始。然后完整详细的解决方案将是：

def one_sort(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    res = [] 
    i, j = 0, len(s) 
    for el in lst: 
     if isinstance(el, str): 
      j -= 1 
      res.append(s[j]) 
     else: 
      res.append(s[i]) 
      i += 1 
    return res 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort(lst)) # [3, 'x', 'b', 5, 6, 'a']

要短得多，但神秘的解决方案将是：

def one_sort_cryptic(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    return [s.pop(-isinstance(el, str)) for el in lst] 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort_cryptic(lst)) # [3, 'x', 'b', 5, 6, 'a']

排序一个清单：数字升序排列，字母降序

相关推荐