如何对一个列表进行排序，使得正数排在负数前面，并且按照各自的值进行排序？

Question

我有一个包含正数和负数混合的列表，如下所示：

lst = [1, -2, 10, -12, -4, -5, 9, 2]

我希望实现的目标是按正数和负数分别排序，将正数排在负数前面，并分别进行排序。

期望的输出：

[1, 2, 9, 10, -12, -5, -4, -2]

我能够解决第一部分：让正数排在负数前面，但不幸的是这并没有分别对正数和负数进行排序。

lst = [1, -2, 10, -12, -4, -5, 9, 2]
lst = sorted(lst, key=lambda o: not abs(o) == o)
print(lst)

>>> [1, 10, 2, 9, -2, -12, -4, -5]

我该如何使用Python实现我想要的排序方法？

- Wondercricket

---

几乎是 https://dev59.com/q2445IYBdhLWcg3wXZIy 的副本，这是一个高度相关的阅读。 - Bhargav Rao

你在意零的位置吗？ - user380772

Answer 1

您可以使用普通排序，然后在0处对列表进行二分：

>>> lst
[1, -2, 10, -12, -4, -5, 9, 2]
>>> from bisect import bisect
>>> lst.sort()
>>> i = bisect(lst, 0)  # use `bisect_left` instead if you want zeroes first
>>> lst[i:] + lst[:i]
[1, 2, 9, 10, -12, -5, -4, -2]

这里的最后一行利用了切片不变式lst == lst[:n] + lst[n:]

另一个选择是使用元组作为排序键，并依赖于元组的字典序排序：字典序

>>> sorted(lst, key=lambda x: (x<0, x))  # use <= instead if you want zeroes last
[1, 2, 9, 10, -12, -5, -4, -2]

- wim

---

有人能向我解释一下那个 lambda 如何工作吗？（或者只是给我一个链接，让我可以阅读相关行为的资料？） - Elliot Roberts

在性能方面，二分法是明显的赢家...值得称赞（需要研究该模块）...词典比二分法要差得多，甚至比双重列表推导还要糟糕。最糟糕的是使用numpy数组，说实话我有点惊讶...可能不得不发帖问一下，因为我没有预料到这一点，也不知道为什么，即使使用了np.sort。 - John Smith

嗯，好奇为什么bisect和numpy数组会变慢后，结果发现如果你的列表“较小”，那么bisect更快，但是如果它很大，那么numpy更快。 - John Smith

我预计它们在渐进情况下都是O(n*log n)，而且我认为没有任何可能比这更好的方法。 - wim

如果列表中包含0，这个会做什么？ - jpmc26

Answer 2

只是比较不同的方法。

结果：

> Shuffle cost comparison small
shuffle_lst: 0.001181483967229724
shuffle_ar: 0.014688121969811618
> Shuffle cost comparison medium
shuffle_lst: 0.572294642101042
shuffle_ar: 0.3266364939045161
> Shuffle cost comparison large
shuffle_lst: 26.5786890439922
shuffle_ar: 6.284286553971469

                    +cost               -cost
bisectme:    0.004252934013493359    0.003071450046263635
lexicon:     0.010936842067167163    0.009755358099937439
compreh.:    0.0071560649666935205   0.005974580999463797
arrayme:     0.03787591797299683     0.023187796003185213
nplexicon:   0.022204622975550592    0.007516501005738974
npbisect:    0.023507782025262713    0.008819660055451095

                    +cost               -cost
bisectme:    7.716002315981314   7.143707673880272
lexicon:     22.17862514301669   21.606330500915647
compreh.:    8.690494343056343   8.118199700955302
arrayme:     1.5029839979251847      1.1763475040206686
nplexicon:   2.0811527019832283      1.7545162080787122
npbisect:    1.3076487149810418      0.9810122210765257

                    +cost               -cost
bisectme:    180.77819497592282      154.19950593193062
arrayme:     22.476932613993995      16.192646060022525
nplexicon:   41.74795828794595   35.46367173397448
npbisect:    20.13856932707131   13.85428277309984

代码：

import sys
import numpy as np
from timeit import timeit
from bisect import bisect
from random import shuffle

def shuffle_lst():
    np.random.shuffle(lst)

def shuffle_ar():
    np.random.shuffle(ar)

def bisectme():
    np.random.shuffle(lst)
    lst.sort()
    i = bisect(lst, 0)
    return lst[i:] + lst[:i]

def lexicon():
    np.random.shuffle(lst)
    return sorted(lst, key=lambda x: (x < 0, x))

def comprehension():
    np.random.shuffle(lst)
    return sorted([i for i in lst if i > 0]) + sorted([i for i in lst if i < 0])

def arrayme():
    np.random.shuffle(ar)
    return np.concatenate([np.sort(ar[ar >= 0]), np.sort(ar[ar < 0])], axis=0)

def nplexicon():
    np.random.shuffle(ar)
    return ar[np.lexsort((ar, ar < 0))]

def numpybisect():
    np.random.shuffle(ar)
    ar.sort()
    i = ar.__abs__().argmin()
    return np.concatenate((ar[i:], ar[:i]))


nloops = 1000

lst = list(range(-10**1, 0, 1)) + list(range(10**1, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison small")
cost_shuffle_list_small = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_small)
cost_shuffle_array_small = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_small)

lst = list(range(-10**4, 0, 1)) + list(range(10**4, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison medium")
cost_shuffle_list_medium = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_medium)
cost_shuffle_array_medium = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_medium)

nloops = 100

lst = list(range(-10**6, 0, 1)) + list(range(10**6, -1, -1))
ar = np.array(lst)
print("> Shuffle cost comparison large")
cost_shuffle_list_large = timeit(shuffle_lst, number=nloops)
print("shuffle_lst:", cost_shuffle_list_large)
cost_shuffle_array_large = timeit(shuffle_ar, number=nloops)
print("shuffle_ar:", cost_shuffle_array_large)

print()

nloops = 1000

## With small lists/arrays
lst = list(range(-10**1, 0, 1)) + list(range(10**1, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o pen.\t\t\t\tw. pen.")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(lexicon, number=nloops)
print("lexicon:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(comprehension, number=nloops)
print("compreh.:\t", foo, "\t", foo - cost_shuffle_list_small)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_small)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_small)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_small)

print()

## With medium lists/arrays
lst = list(range(-10**4, 0, 1)) + list(range(10**4, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o cost\t\t\t\tw. cost")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(lexicon, number=nloops)
print("lexicon:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(comprehension, number=nloops)
print("compreh.:\t", foo, "\t", foo - cost_shuffle_list_medium)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_medium)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_medium)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_medium)

print()


## With large lists/arrays
nloops = 100

lst = list(range(-10**6, 0, 1)) + list(range(10**6, -1, -1))
ar = np.array(lst)

print("\t\t\t\t\tw/o cost\t\t\t\tw. cost")

foo = timeit(bisectme, number=nloops)
print("bisectme:\t", foo, "\t", foo - cost_shuffle_list_large)

foo = timeit(arrayme, number=nloops)
print("arrayme:\t", foo, "\t", foo - cost_shuffle_array_large)

foo = timeit(nplexicon, number=nloops)
print("nplexicon:\t", foo, "\t", foo - cost_shuffle_array_large)

foo = timeit(numpybisect, number=nloops)
print("npbisect:\t", foo, "\t",  foo - cost_shuffle_array_large)

print()

- John Smith

---

np.sort(ar) 占用了 3/4 的时间；只有 1/4 的时间用于掩码和连接。 - hpaulj

我不确定以下事实是否公平：1）列表已经预先排序；2）即使没有预先排序，bisectme 也会就地对列表进行排序，影响所有后续测试。 - jpmc26

210^2=200，而且200更容易阅读和书写。但当你写210^2时，会让你看起来非常聪明。 - Tsahi Asher

@JohnSmith 这仍然在第一个循环中对列表进行排序，然后它在所有后续循环中都已排序。这可能会给原地排序带来不公平的优势。每个循环都需要自己的副本。 - jpmc26

啊，是的...被误解了，你的意思是每个timeit循环中的循环...没错...将洗牌移动到每个函数中...这需要一段时间才能运行...完成后会更新。 - John Smith

@jpmc26 现在怎样……这个修复了你的意思吗？但结果是……好吧，就让它们保持现状吧…… - John Smith

Answer 3

创建两个列表，一个包含正数，另一个包含负数，然后按照您喜欢的方式对每个列表的内容进行排序。例如：

my_list = [1, -2, 10, -12, -4, -5, 9, 2]
pos_list, neg_list = [], []
for item in my_list:
    if item < 0: 
        neg_list.append(item)
    else:
        pos_list.append(item)

final_list = sorted(pos_list) + sorted(neg_list)

- Moinuddin Quadri

Answer 4

您可以通过对元素的倒数取反进行排序：

from __future__ import division

sorted(lst, key=lambda i: 0 if i == 0 else -1 / i)

对数取反会交换数量级的顺序（中间是更大的数字，外面是更小的数字）。取负数会颠倒顺序（正数在前，负数在后）。

当然要注意你的数字的大小，以及它们是否会导致任何溢出或下溢问题。

- jpmc26

---

对于像上面那样的2*10^4个未排序列表，这也很慢（约60秒）。 - John Smith

@JohnSmith 是的，不是超级快，但简单而且相当直观。 - jpmc26

聪明的想法！一眼看到f(x)=-1/x的图表，帮助我理解了它的工作原理。 - wim

Answer 5

创建两个分离的列表。一个存储正数，一个存储负数。对负数列表进行排序，然后将它们连接在一起：

>>> lst = [1, -2, 10, -12, -4, -5, 9, 2]
>>> sorted([i for i in lst if i > 0]) + sorted([i for i in lst if i =< 0])
[1, 2, 9, 10, -12, -5, -4, -2]
>>> 

- Christian Dean

---

你的比较中应该包括对0的检查，使用>= 0或<= 0来包含0。 - pilkch

Answer 6

import numpy as np
lst = [1, -2, 10, -12, -4, -5, 9, 2]
ar = np.array(lst)
lst = list(np.concatenate([np.sort(ar[ar >= 0]), np.sort(ar[ar < 0], reverse = True)], axis = 0))
print(lst)

如果您不必使用列表，但满意于numpy数组，则无需支付转换成本，即。

import numpy as np
ar = np.array([1, -2, 10, -12, -4, -5, 9, 2])
ar = np.concatenate([np.sort(ar[ar >= 0]), np.sort(ar[ar < 0])], axis = 0)
print(ar)

- John Smith

---

虽然 numpy 看起来是一个很棒的模块，但它似乎对我想要完成的任务来说有些过度。 - Wondercricket

嗯，好奇为什么bisect和numpy数组会变慢后，结果发现如果你的列表“较小”，那么bisect更快，但是如果它很大，那么numpy更快。 - John Smith

Answer 7

import numpy as np

l = np.array([1, -2, 10, -12, -4, -5, 9, 2])
l[np.lexsort((l, l < 0))]

array([  1,   2,   9,  10, -12,  -5,  -4,  -2])

- piRSquared

Answer 8

赞赏 wmin 的解决方案逻辑（被接受的答案）非常好。为了完整起见，基于 numpy 的类似答案也是如此，它在除了小列表/数组之外的任何其他情况下都要快得多，具体如下：

lst = [1, -2, 10, -12, -4, -5, 9, 2]
ar = np.array(lst)
ar.sort()
i = ar.__abs__().argmin()
np.concatenate((ar[i:], ar[:i]))

- John Smith

Answer 9

我不知道是否最符合Python的风格，但它肯定没有过多的花哨内容。在我看来，这是一段清晰易懂的代码：

lst = [1, -2, 10, -12, -4, -5, 9, 2]

pos = list()
neg = list()

for i in lst:
    neg.append(i) if i < 0 else pos.append(i)

print(sorted(pos) + sorted(neg))

- boardrider

Answer 10

将列表原地排序两次，如下：

lst = [1, -2, 10, -12, -4, -5, 9, 2]
lst.sort()
lst.sort(key=int(0).__gt__)      # key is True for items <= 0

这利用了Python的sort函数/方法是稳定的这一事实。这意味着具有相同值或键的项目保持相同的顺序。第一次排序将所有项目按从小到大的顺序排列。对于第二次排序，所有< 0的项目都会获得True的键，所有> = 0的项目都会获得False的键。因为True（1）> False（0），所以第二次排序将所有负数项目移到末尾，而不改变负数项目的顺序。

- RootTwo