归并排序功能（自然归并排序）

Question

有几种方法可以进行合并排序，但我特别需要它像自然合并排序一样工作。该算法会在文件中生成较小的数字列表，如下所示：

原始列表： 35 27 24 28 31 37 1 4 7 6 8 9

较小的列表部分： [35], [27], [24, 28 ], [31, 37], [1, 4, 7], [6, 8, 9]

正如你所注意到的，每次遇到未排序的列表如果数字小于当前值，则会创建一个新单位。一旦列表结束，该列表就会以另一种方式分成两个其他列表：

第一个列表： [35], [24, 28], [1, 4, 7]

第二个列表： [27], [31, 37 ], [6, 8, 9]

最后一步涉及将两个列表再次拉到一起，并在遍历时比较第一个列表项和第二个列表项中的单位之间的值。例如，列表一中的第一个单元与列表二中的第一个单元进行比较，并保持数字的顺序。任何剩余的单位将添加到末尾（未显示）。

合并两个列表：[27, 35], [24, 28, 31, 37], [1, 4, 6, 7, 8, 9]

重复此过程，直到列表按一个单元排序。

除了合并两个列表之外，我已经在该算法中设置了所有内容，并且可以正常工作，并且调试或定位问题非常困难。在进入分段错误之前，它大约进行了一半。不管怎样，我不能在这个程序上使用归并排序STL，它都在一个链接列表中。

注意：构造函数和其他必要的函数已经就位。我故意省略了其他功能以体现特定功能。

class mergeList
{
   public:

      //Setters
      void setNumber(int item);
      void setStart(bool newStatus);
      void setEnd(bool newStatus);
      void setPrev(mergeList* node);
      void setNext(mergeList* node);

      //Getters
      int getNumber();
      bool getStart();
      bool getEnd();
      mergeList* getPrev();
      mergeList* getNext();

   private:
      int number;

      bool startSection;
      bool endSection;

      mergeList* prev;
      mergeList* next;
};

class mergeListObject
{
   public:
     mergeList* firstNode;
     mergeList* lastNode;

   void mergeLists(mergeListObject &firstList,
                   mergeListObject &secondList);

   //Other functions in program are in here.
};

void mergeListObject::mergeLists(mergeListObject &firstList,
                                 mergeListObject &secondList)
{
   mergeList* combTraverse = firstNode;
   mergeList* firstTraverse = firstList.firstNode;
   mergeList* secondTraverse = secondList.firstNode;

   bool listDone = false;

   //This will clear the combination list for insertion
   while (combTraverse != NULL)
   {
      combTraverse->setNumber(-1);
      combTraverse->setStart(false);
      combTraverse->setEnd(false);

      combTraverse = combTraverse->getNext();
   }

   combTraverse = firstNode;

   combTraverse->setStart(true);

   while (listDone == false)
   {
      //This will go until the first list is traversed.
      do
      {
         bool exception = false;

         int j = firstTraverse->getNumber();
         int k;

         //If the second list is still active, this will
         //grab its current value for comparison.
         if (secondTraverse != NULL)
            k = secondTraverse->getNumber();

         //Second list is done, will automatically grab
         //first list's value and traverse through to the end.
         if (secondTraverse == NULL)
            combTraverse->setNumber(firstTraverse->getNumber());

         else
         {
            //Both values from both lists are compared.
            if (j <= k)
               combTraverse->setNumber(firstTraverse->getNumber());

            else
            {
                exception = true;
                combTraverse->setNumber(secondTraverse->getNumber());
            }
         }

         //If the first value unit was used, move the first list iterator up.
         //Otherwise, the second list's iterator moves up.
         if (exception == false)
            firstTraverse = firstTraverse->getNext();

         else
            secondTraverse = secondTraverse->getNext();

         exception = false;
      }
      while (firstTraverse->getEnd() == false);

      //If the second list isn't done, this will finish it.
      do
      {
         combTraverse->setNumber(secondTraverse->getNumber());

         secondTraverse = secondTraverse->getNext();
         combTraverse = combTraverse->getNext();
      }
      while (secondTraverse->getEnd() == false);

      combTraverse->setEnd(true);

      //Marks the end of the section and sets the next one,
      //considering it isn't the end of the list.
      if (combTraverse->getNext() != NULL)
         combTraverse->getNext()->setStart(true);

      //Both of these should end up at the start of a unit in their own lists.
      firstTraverse = firstTraverse->getNext();
      secondTraverse = secondTraverse->getNext();

      //Are both lists done?
      if (firstTraverse == NULL &&
          secondTraverse == NULL)
         listDone = true;
   }

   return;
}

int main()
{
   mergeListObject one;
   mergeListObject two;
   mergeListObject combined;

   //The two lists are already separated. All
   //other functions have already been called.

   combined.mergeLists(one, two);

   return 0;
} 

Answer 1

我发现的第一个错误是在合并函数的末尾：

firstTraverse = firstTraverse->getNext();
secondTraverse = secondTraverse->getNext();

可能会生成运行时错误（“访问冲突”或“分段错误”，具体取决于编译器和操作系统），您必须更改它以

if (firstTraverse)
    firstTraverse = firstTraverse->getNext();
if (secondTraverse)
    secondTraverse = secondTraverse->getNext();

注意这些指针实际上可以为 NULL。

您还必须将 while (firstTraverse->getEnd() == false); 更改为 while(firstTraverse & firstTraverse->getEnd() == false); 同样，只要第一个列表的分区数量少于第二个列表，firstTravers 就可以为 NULL。