如何基于二分搜索实现自然排序的有序列表插入操作？

我用二分搜索向有序列表插入元素，现有代码能实现字母数字排序，但没法做自然排序。其中键name是数值与文本混合的内容，当前按字母顺序排序会让数字按字符串顺序（而非数值顺序）排列。能不能实现按自然排序插入元素？

举个例子：
要插入的元素列表：

{ "Orange", "Frog", 3, 4, 55}
{ 3031, "Bob", 21, 4, 56 }
{ 400, "Tree", 6, 66, 75}

期望的最终排序结果：

{ 400, "Tree", 6, 66, 75}
{ 3031, "Bob", 21, 4, 56 }
{ "Orange", "Frog", 3, 4, 55}

当前使用的代码：

def binSearch(listSearch, name):
    low = 0  
    high = len(listSearch) 
    mid = 0

    while low < high:  
        # 获取整数结果   
        mid = (high + low) // 2  

        # 检查name是否在mid位置   
        if listSearch[mid].name < name:
            low = mid + 1 
        else:
            high=mid

当前代码得到的结果：

{ 3031, "Bob", 21, 4, 56 }
{ 400, "Tree", 6, 66, 75}
{ "Orange", "Frog", 3, 4, 55 }

当然可以实现自然排序的插入，核心是替换原有的字符串比较逻辑，改用自然排序规则来对比name字段。

实现思路 #

自然排序会把字符串中的数字部分当作数值来比较，比如"400"会排在"3031"前面（因为400 < 3031），而不是按字符串顺序让"3031"在前（因为"3"的ASCII码小于"4"）。

可以自己实现自然排序的比较逻辑，或者利用Python标准库外的natsort模块（若允许使用第三方库）。

方法1：手动实现自然排序比较逻辑

先写一个辅助函数，把name拆分为文本和数字分段，再逐段比较：

def natural_key(s):
    # 将字符串拆分为文本和数字部分
    import re
    parts = re.split(r'(\d+)', str(s))
    # 数字部分转整数，文本部分转小写（可选，用于不区分大小写比较）
    return [int(part) if part.isdigit() else part.lower() for part in parts]

修改二分搜索中的比较逻辑，用这个natural_key来对比：

def binSearch(listSearch, name):
    low = 0  
    high = len(listSearch) 
    mid = 0
    target_key = natural_key(name)

    while low < high:  
        mid = (high + low) // 2  
        current_key = natural_key(listSearch[mid].name)
        # 用自然排序的key做比较
        if current_key < target_key:
            low = mid + 1 
        else:
            high = mid
    return low  # 返回元素应该插入的位置

方法2：使用natsort库（更简洁）

如果可以安装第三方库，直接用natsort的natsort_keygen生成排序key：

from natsort import natsort_keygen

natural_key = natsort_keygen()

def binSearch(listSearch, name):
    low = 0  
    high = len(listSearch) 
    mid = 0
    target_key = natural_key(name)

    while low < high:  
        mid = (high + low) // 2  
        current_key = natural_key(listSearch[mid].name)
        if current_key < target_key:
            low = mid + 1 
        else:
            high = mid
    return low

验证效果 #

用修改后的binSearch获取插入位置，将元素插入后，就能得到你期望的自然排序结果：

{ 400, "Tree", 6, 66, 75}
{ 3031, "Bob", 21, 4, 56 }
{ "Orange", "Frog", 3, 4, 55}

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