如何对整数中的数字排序？是否有比转数组调用.sort()更高效的方法？

常规实现：转字符串/数组后调用通用排序 #

这是最直观易读的实现方式，适合大多数日常场景，代码简洁、维护成本低。以Python为例：

def sort_digits(n):
    num_str = str(abs(n))
    sorted_chars = sorted(num_str)
    sorted_num = int(''.join(sorted_chars))
    return sorted_num if n >= 0 else -sorted_num

这种方法的时间复杂度是O(k logk)（k为数字的位数），因为底层的sorted()通常采用Timsort这类比较类排序算法，虽然实现高效，但对于数字各位这种范围极小的场景，还有优化空间。

性能更优的实现：计数排序 #

由于数字的每一位只能是0-9，范围固定且极小，计数排序是性能最优的选择，时间复杂度仅为O(k)，空间复杂度为O(1)（固定大小的计数数组）。

字符串版实现

def sort_digits_counting(n):
    is_negative = n < 0
    num_str = str(abs(n))
    count = [0] * 10
    
    # 统计每个数字出现的次数
    for c in num_str:
        count[int(c)] += 1
    
    # 生成升序结果（降序则遍历range(9, -1, -1)）
    sorted_str = ''.join(str(digit) * count[digit] for digit in range(10))
    return int(sorted_str) if not is_negative else -int(sorted_str)

纯数学版实现（无字符串转换）

如果想避免字符串操作的开销，也可以用纯数学方法逐位统计并重构数字：

def sort_digits_math(n):
    is_negative = n < 0
    num = abs(n)
    count = [0] * 10
    
    # 统计每一位数字的出现次数
    while num > 0:
        digit = num % 10
        count[digit] += 1
        num = num // 10
    
    # 重构排序后的数字（升序）
    sorted_num = 0
    for digit in range(10):
        for _ in range(count[digit]):
            sorted_num = sorted_num * 10 + digit
    
    return sorted_num if not is_negative else -sorted_num

方案选择建议 #

• 若优先考虑代码可读性和开发效率，转数组调用sorted()完全够用，在位数不多的场景下性能差异可以忽略。
• 若需要处理大量长位数数字、追求极致性能，计数排序实现是最优解，它利用数字范围有限的特性，彻底规避了比较类排序的O(k logk)开销。

内容的提问来源于stack exchange，提问作者anonymous