对数组升序排序，末尾有重复项也按升序排序

Question

我试图对像 [3,2,1,2,4,5,3] 这样的数组进行排序，以便它按升序排序，但所有重复项按排序顺序分组在末尾。因此数组的结果将是 [1,4,5,2,2,3,3]。在不使用 python 内置 sort() 的情况下如何做到这一点？

Answer 1

您可以将

key

参数指定为元组（值是否重复，值本身）：

sort(l, key=lambda v: (l.count(v) > 1, v))

UPD：这对于较小的列表来说很好。然而，正如 @Stef 在评论中提到的，这个解决方案具有二次复杂度（准确地说是 N^2 * log(N) ），而你可以线性地做到这一点（N * log(N)）：

from collections import Counter
c = Counter(l)
sort(l, key=lambda x: (c[x] > 1, x))

Answer 2

分两个阶段进行。

1. 只需使用您最喜欢的就地排序算法对数组进行就地排序
2. 从右向左扫描排序数组，找到第一个

   DU

   子数组（其中

   D

   是一堆重复值，

   U

   是唯一元素的尾部）。把它变成

   UD

   。继续前进。

第二阶段于

O(n)

完成。