如何不使用Python内置sort方法按字符串前4位排序字符串列表

现有如下格式的字符串列表：

source_1 = [
    "2012 18  B",
    "2015 19  B",
    "2007 948 D",
    "2018 179 C"
]

需要自定义函数实现排序，要求不得调用Python内置的sort/sorted相关排序方法，排序规则为按每个字符串的前4个字符升序排列，期望输出结果如下：

source_1 = [
    "2007 948 D",
    "2012 18  B",
    "2015 19  B",
    "2018 179 C"
]

原有实现代码运行效率过低，需要优化方案。

你之前写的实现有三个明显缺陷：

• 时间复杂度太高，达到O(n³)：每插入一个元素就执行一次双层循环的全量冒泡排序，数据量稍大时性能会极差
• 返回结果不符合预期：代码只截取了字符串前10位存入结果列表，丢失了原字符串后半段内容，无法返回完整的原字符串排序结果
• 逻辑冗余：排序规则只需要对比前4个字符，不需要额外截取字符串后6位、前10位的操作

不使用内置排序方法的前提下，选择平均时间复杂度为O(nlogn)的快速排序实现即可，性能远高于原嵌套冒泡逻辑，可参考以下代码：

def sorttimestamp(arr):
    # 递归终止条件：列表长度不超过1时天然有序，直接返回
    if len(arr) <= 1:
        return arr
    # 取列表中间元素作为排序基准
    pivot = arr[len(arr) // 2]
    pivot_key = pivot[:4]
    left_part = []
    equal_part = []
    right_part = []
    # 遍历列表按对比key拆分到三个子列表
    for item in arr:
        current_key = item[:4]
        if current_key < pivot_key:
            left_part.append(item)
        elif current_key > pivot_key:
            right_part.append(item)
        else:
            equal_part.append(item)
    # 递归排序左右子列表后拼接得到最终结果
    return sorttimestamp(left_part) + equal_part + sorttimestamp(right_part)

调用测试：

source_1 = [
    "2012 18  B",
    "2015 19  B",
    "2007 948 D",
    "2018 179 C"
]
sorted_source = sorttimestamp(source_1)
print(sorted_source)

运行输出和预期完全一致：

['2007 948 D', '2012 18  B', '2015 19  B', '2018 179 C']

• 基于快速排序思想实现，平均时间复杂度O(nlogn)，相比原实现的O(n³)性能提升非常明显，处理万级以上数据量也不会有明显延迟
• 全程保留原字符串完整内容，不会出现内容截断丢失的问题
• 对比时仅取每个字符串前4个字符作为排序依据，完全匹配规则要求
• 逻辑简洁，没有冗余的字符串截取、无效循环操作

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