按数字对数字进行排序

Question

我必须对一个整数向量进行排序（所有整数的长度都相同）。具有相同第一个数字的整数必须相对于第二个数字进行排序，并且具有相同数字的数字：第一个和第二个数字按第三个数字等排序。此外，后续数字交替排序（一次升序和一次降序）

所以当我有 lis = [137, 944, 972, 978, 986], 我应该得到 sorted_lis = [137, 986, 972, 978, 944]

我知道如何通过选择数字 (a) 来排序

lis.sort(key=lambda x: int(str(x)[a]))

我试过使用插入排序，（因为我必须使用稳定的排序算法）

def insertion_sort(list):
    for i in range(len(list)):
        key = list[i]
        j = i-1
        while j >= 0 and key < list[j]:
            list[j+1] = list[j]
            j -= 1
        list[j+1] = key

    return list

Answer 1

您可以定义一个key如下：

lis = [137, 944, 972, 978, 986]

def alternate_digits(x):
    return [-d if i % 2 else d for i, d in enumerate(map(int, str(x)))]

output = sorted(lis, key=alternate_digits)
print(output) # [137, 986, 972, 978, 944]

键alternate_digits，例如将12345转换为[1, -2, 3, -4, 5]。

Answer 2

解决方案 1：使用整数进行多重排序

一个有趣的 multisort 利用 list.sort 稳定的优势（如排序指南部分所述）：

lis = [137, 944, 972, 978, 986]

pow10 = 1
while pow10 <= lis[0]:
    lis.reverse()
    lis.sort(key=lambda x: x // pow10 % 10)
    pow10 *= 10

print(lis)  # [137, 986, 972, 978, 944]

这首先按最后一位排序，然后按 second-to-last，依此类推，直到按第一位排序。并在排序之间反转。

解决方案 2：每隔一个数字“取反”

另一种方法，例如将 1234 转换为 1735（每隔一个数字“取反”，即从 9 中减去）：

def negate_every_second_digit(x):
    result = 0
    pow10 = 1
    while x:
        result = (x % 10 + 1) * pow10 - (result + 1)
        pow10 *= 10
        x //= 10
    return result
lis.sort(key=negate_every_second_digit)

解决方案 3：对字符进行多重排序

与您的尝试类似，但仅转换为字符串一次（代价是最后一次转换回整数）：

lis[:] = map(str, lis)
for i in reversed(range(len(lis[0]))):
    lis.reverse()
    lis.sort(key=itemgetter(i))
lis[:] = map(int, lis)

您的解决方案，已完成

正如您所说，您已经知道如何按某个数字排序。您只需要为每个人执行此操作：

digits = len(str(lis[0]))
for a in reversed(range(digits)):
    lis.sort(key=lambda x: int(str(x)[a]),
             reverse=a % 2)

基准

100,000 个随机 six-digit 数字的基准：

Kelly1  201 ms  192 ms  196 ms
Kelly2  160 ms  154 ms  157 ms
Kelly3  248 ms  237 ms  243 ms
j1_lee  394 ms  396 ms  404 ms
OSA     409 ms  405 ms  419 ms

基准代码(Try it online!):

def Kelly1(lis):
    pow10 = 1
    while pow10 <= lis[0]:
        lis.reverse()
        lis.sort(key=lambda x: x // pow10 % 10)
        pow10 *= 10

def Kelly2(lis):
    def negate_every_second_digit(x):
        result = 0
        pow10 = 1
        while x:
            result = (x % 10 + 1) * pow10 - (result + 1)
            pow10 *= 10
            x //= 10
        return result
    lis.sort(key=negate_every_second_digit)

def Kelly3(lis):
    lis[:] = map(str, lis)
    for i in reversed(range(len(lis[0]))):
        lis.reverse()
        lis.sort(key=itemgetter(i))
    lis[:] = map(int, lis)

# Modified by Kelly to sort in-place, as the question and my solutions do
def j1_lee(lis):
    def alternate_digits(x):
        return [-d if i % 2 else d for i, d in enumerate(map(int, str(x)))]
    lis.sort(key=alternate_digits)

# The question's attempt, completed by Kelly.
def OSA(lis):
    digits = len(str(lis[0]))
    for a in reversed(range(digits)):
        lis.sort(key=lambda x: int(str(x)[a]),
                 reverse=a % 2)

sorts = Kelly1, Kelly2, Kelly3, j1_lee, OSA

from timeit import timeit
import random
from operator import itemgetter

n = 100_000
digits = 6

times = {sort: [] for sort in sorts}
for _ in range(3):
    lis = random.choices(range(10**(digits-1), 10**digits), k=n)
    expect = None
    for sort in sorts:
        copy = lis.copy()
        time = timeit(lambda: sort(copy), number=1)
        times[sort].append(time)
        if expect is None:
            expect = copy
        else:
            assert copy == expect
for sort in sorts:
    print(f'{sort.__name__:6}',
          *(' %3d ms' % (t * 1e3) for t in times[sort]))

按数字对数字进行排序

Sort a number by its digits

python

sorting

解决方案 1：使用整数进行多重排序

解决方案 2：每隔一个数字“取反”

解决方案 3：对字符进行多重排序

您的解决方案，已完成

基准