改进我的链表合并排序。如何？

Question

在我深入解释之前，您应该意识到以下代码可能非常糟糕。我大约两个月前开始编程（时时有几个小时）。所以我缺乏经验，我的编码风格还有待改进，但我仍然怀念实践和大量（基本）知识。这也包括我可能用错误的名字来称呼事物:)。

我对算法（大学）很感兴趣，并且想练习一些指针处理（最初遇到了很多问题），所以我决定使用单链表进行合并排序，看看它与我教授的合并排序算法相比表现如何（对数组进行排序）。不，这不是家庭作业（我的大学课程（电气工程）都没有家庭作业）——这是我对算法、C 和简单练习的理解的提高。

---

我的代码已经可以工作了。出于测试目的，我总是创建反向排序列表。对于列表为 NULL 的情况，它仍然缺少一些东西。

因此，在发布代码之前，这就是我正在使用的结构：

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

我有两个函数，mergeSort 和 merge。 mergeSort 返回已排序（子）列表的新头，而 merge 返回合并序列的头。

现在我给 mergeSort 未排序列表的当前头部和元素数量。 然后它递归地分解列表（显然:)）。 我不确定下面的代码要说多少。如果有不清楚的地方，我会尽快回答和解释，但是

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

merge 接收两个子列表的头（它们要么是一个元素，要么是已经排序的序列）以及第一个和第二个列表的元素。

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

因此，我欢迎任何关于我所做的愚蠢的事情的评论，我没有考虑可能的问题，一些输入代码破坏代码或如何做得更好，我确信还有很多改进的可能性。提前致谢。

Answer 1

排序合并阶段的“正常”结构是：

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

“移动”操作包括更新指向列表中下一项的指针。

您的 merge() 函数的结构有些不同。

要求对列表进行计数也是一种惯例。通常，您可以使用“next is null”或“next is head”来确定列表的末尾，具体取决于列表是纯线性列表还是循环列表。