C语言链表按字符串排序不稳定的修复与算法选型咨询

一、修改现有代码实现稳定排序的方法 #

完全可以修改现有插入排序代码实现稳定排序。当前代码不稳定的根源是相同m_Name的节点插入时破坏了原相对顺序：原逻辑中只要已排序节点的m_Name大于等于新节点，就把新节点插在前面，导致后出现的同键值节点跑到前面去了。

修改只需调整两处比较逻辑，保证同键值节点的相对顺序不变：

TITEM *sortInsert(TITEM *newNode, TITEM *sorted) {
    // 仅当已排序节点m_Name严格大于新节点时，才插在头部
    if (!sorted || strcmp(sorted->m_Name, newNode->m_Name) > 0) {
        newNode->m_Next = sorted;
        sorted = newNode;
    } else {
        TITEM *tmp = sorted;
        // 遍历到第一个m_Name大于新节点的前驱，同键值时继续向后走
        while (tmp->m_Next && strcmp(tmp->m_Next->m_Name, newNode->m_Name) <= 0) {
            tmp = tmp->m_Next;
        }
        newNode->m_Next = tmp->m_Next;
        tmp->m_Next = newNode;
    }
    return sorted;
}

修改后，同m_Name的节点会被插入到已有同键值节点的末尾，完全保留原链表中的相对顺序，实现稳定排序。另外原代码的降序逻辑（排序后反转）不会破坏稳定性，因为反转只是整体颠倒顺序，同键值节点的相对位置仍保持不变。

二、不修改现有代码时的替代稳定排序算法 #

如果不改造现有插入排序，适合链表的稳定排序算法（禁止使用库函数）有：

• 归并排序：天生稳定，且对链表结构极度友好——不需要额外开辟存储空间，直接通过调整指针完成合并操作，时间复杂度O(nlogn)，是大数据量链表排序的最优选择。
• 冒泡排序：稳定但效率低下（时间复杂度O(n²)），仅适合节点数量极少的链表场景。

三、链表稳定排序学习方向 #

• 深入理解稳定排序的核心定义：相同键值的元素在排序前后的相对位置不发生改变。
• 学习链表归并排序的分治实现：拆分链表、递归排序子链表、合并两个有序链表（合并阶段严格保证同键值节点的顺序）。
• 研究插入排序的稳定化改造逻辑：核心是控制同键值元素的插入位置，避免打乱原顺序。

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