我必須對整數向量進行排序（所有整數都具有相同的長度）。具有相同第一位數字的整數必須相對于第二位數字進行排序，并且具有相同的數字：第一位和第二位數字按第三位數字等排序。此外，后續數字交替排序（一次升序和一次降序）
所以當我有時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
uj5u.com熱心網友回復：
解決方案 1：使用整數進行多排序
一個有趣的多排序，利用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]
這首先按最后一個數字排序，然后按倒數第二個等，直到按第一個數字排序。并在種類之間反轉。
解決方案 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 個隨機六位數為基準：
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
基準代碼（在線試用！）：
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}',
*(' = ms' % (t * 1e3) for t in times[sort]))
uj5u.com熱心網友回復：
您可以按如下方式定義密鑰：
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].
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/476938.html