C - 按字符串排序链表

Question

我有一个程序可以按字符串(m_Name 值)对链表进行排序。问题是程序不稳定(我的意思是:https://www.geeksforgeeks.org/stable-and-unstable-sorting-algorithms/)。

有什么方法可以修复我的代码以使排序稳定，还是我应该创建一些其他算法。或者，如果我不能将任何库用于 qsort 等，您知道哪种算法是合适的吗？

所有节目https://onecompiler.com/c/3ysjeqn5j

或者如果有任何我可以研究的 Material 来创建链表的稳定排序算法，请告诉我。

TITEM *sortInsert(TITEM *newNode, TITEM *sorted) {
    //if (sorted || strcmp(sorted->m_Name, newNode->m_Name) == 0)
    //    return sorted;

    if (!sorted || strcmp(sorted->m_Name, newNode->m_Name) >= 0) {
        newNode->m_Next = sorted;
        sorted = newNode;
    } else { //Locate the node before the point of insertion
        TITEM *tmp = sorted;
   
        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;
}

TITEM *sortList(TITEM *l, int ascending) {
    TITEM *tmp = l;
    TITEM *sorted = NULL;

    while (tmp) {
        TITEM *next = tmp->m_Next;
        sorted = sortInsert(tmp, sorted);
        tmp = next;
    }
    l = sorted;

    if (!ascending) {
        l = reverse(l);
    }

    return l;
}

Answer 1

您的方法有两个问题:

• 您一次一个地将列表中的元素插入排序列表中，因此如果该元素与排序列表中已有的元素相同，则应将其插入之后重复以保持相同的相对顺序。您必须将比较运算符更改为 >和 <=分别。

• 您不能通过颠倒列表来处理降序，因为重复的元素也会以相反的顺序出现。一个简单的解决方案是传递排序方向并乘以 strcmp() 的返回值通过 1或 -1取决于方向。重复项将按原始相对顺序保留为 strcmp。返回 0对他们来说是双向的。

修改后的版本:

// insert a node according to sorting direction
TITEM *sortInsert(TITEM *newNode, TITEM *sorted, int dir) {
    if (!sorted || strcmp(sorted->m_Name, newNode->m_Name) * dir > 0) {
        newNode->m_Next = sorted;
        sorted = newNode;
    } else { //Locate the node before the point of insertion
        TITEM *tmp = sorted;
   
        while (tmp->m_Next && strcmp(tmp->m_Next->m_Name, newNode->m_Name) * dir <= 0) {
            tmp = tmp->m_Next;
        }
        newNode->m_Next = tmp->m_Next;
        tmp->m_Next = newNode;
    }
    return sorted;
}

TITEM *sortList(TITEM *l, int ascending) {
    int dir = ascending ? 1 : -1;
    TITEM *tmp = l;
    TITEM *sorted = NULL;

    while (tmp) {
        TITEM *next = tmp->m_Next;
        sorted = sortInsert(tmp, sorted, dir);
        tmp = next;
    }
    return sorted;
}