HackerRank bigSorting问题：Python排序代码超时原因及相关疑问

我正在解决HackerRank的bigSorting问题，题目要求：给定一个由正数字符串组成的数组，每个字符串对应1到10^6位的整数，需按整数值的非降序（升序）排序后返回数组。

我知道以下实现可以通过所有测试用例：

def bigSorting(unsorted):
    return sorted(unsorted, key=int)

但我最初写的代码在部分测试用例中出现超时：

def bigSorting(unsorted):
    int_unsorted = [int(i) for i in unsorted]
    int_sorted = sorted(int_unsorted)
    return [str(i) for i in int_sorted]

我的代码分为三步：1. 字符串转整数；2. 排序；3. 整数转字符串。两种实现的时间复杂度都是O(n log n)，但为何我的代码会超时？我有以下疑问：

• Q1. sorted(unsorted, key=int)是不是避免了第三步的整数转字符串转换？
• Q2. 如果Q1答案为是，这是不是我的代码超时的唯一原因？我的代码还有其他额外开销吗？
• Q3. 使用key参数的sorted会不会在排序时多次将同一个字符串转换为整数？还是每个元素仅转换一次？

疑问解答 #

Q1 解答 #

是的，sorted(unsorted, key=int)完全避免了第三步的int转str操作。这个方式直接对原字符串数组排序，仅用int(i)作为比较的依据，最终返回的仍是原字符串元素，不需要把排序后的整数再转回字符串。

Q2 解答 #

这不是唯一原因，你的代码还有额外的内存和遍历开销：

• 内存开销：你先把所有字符串转成整数存入int_unsorted数组，对于10^6位的超大整数，Python的int对象会占用大量内存。当数组元素数量较多时，额外的内存占用会显著增加，甚至可能触发内存交换，拖慢整体运行速度。
• 两次全量遍历转换：你的代码需要先遍历一次数组完成str→int转换，排序后再遍历一次完成int→str转换。而key=int的方式仅在排序前为每个元素计算一次key值，没有额外的两次全量遍历转换操作。

Q3 解答 #

每个元素仅会被转换一次。Python的sorted函数使用key参数时，会预先为所有元素计算一次key值并缓存，排序过程中直接使用缓存的key进行比较，不会重复转换同一个元素，这也是key参数高效的核心原因之一。

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