链表排序程序提交后提示‘排序不稳定’问题求助

问题描述 #

开发链表排序程序，测试反馈“排序不稳定”。排序规则：ascending=0时执行降序排序，其他值执行升序排序，排序采用区分大小写的字母序。相关代码片段如下：

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;
}

问题根源 #

1. 升序插入逻辑破坏稳定性：
   稳定排序要求相等元素保持原有相对顺序，但原代码中strcmp(sorted->m_Name, newNode->m_Name) >= 0的条件，当元素相等时（strcmp返回0），会将新节点插入到当前节点前面，直接打乱了原顺序。
2. 降序反转操作破坏稳定性：
   先升序排序再反转链表的方式，会颠倒所有元素的顺序，包括原本相等元素的相对位置，进一步破坏稳定性。

修复方案 #

1. 修复升序插入的稳定性 #

修改sortInsert的判断条件，仅在当前节点元素严格大于新节点时才插在前面；相等元素则遍历到所有相等元素的末尾再插入，保留原顺序：

TITEM *sortInsert( TITEM *newNode, TITEM *sorted)
{
    if( !sorted || strcmp(sorted->m_Name, newNode->m_Name) > 0 )
    {
      newNode->m_Next = sorted;
      sorted = newNode;
    }
    else
    {
      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;
}

2. 修复降序排序的稳定性 #

放弃“先升序再反转”的方式，直接根据排序方向调整插入逻辑，保证相等元素的相对顺序：

// 新增带排序方向的插入函数
TITEM *sortInsertWithOrder( TITEM *newNode, TITEM *sorted, int ascending )
{
    if( !sorted )
    {
      newNode->m_Next = sorted;
      sorted = newNode;
    }
    else if( ascending )
    {
      // 升序规则：当前节点>新节点时插前面，相等则往后找
      if( strcmp(sorted->m_Name, newNode->m_Name) > 0 )
      {
        newNode->m_Next = sorted;
        sorted = newNode;
      }
      else
      {
        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;
      }
    }
    else
    {
      // 降序规则：当前节点<新节点时插前面，相等则往后找
      if( strcmp(sorted->m_Name, newNode->m_Name) < 0 )
      {
        newNode->m_Next = sorted;
        sorted = newNode;
      }
      else
      {
        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 = sortInsertWithOrder(tmp, sorted, ascending);
    tmp = next;
  }
  return sorted;
}

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