C语言归并算法详解

归并排序也是一种分割处理式的排序算法，它是由Johnyon Neumann于1945年提出的。

在归并排序算法中，将待排序数据看作是一个链表序列，每个链表(最坏的情况下每个链表中只有一个元素)中的数据都已经排好序，然后不断地将相邻的链表合并为一些较大的链表，当所有的链表都合并为一个链表时，排序过程也就结束了。归并排序算法特别适合于对键表或其它非数组形式的数据结构进行排序，它还能对无法放入内存的数据进行排序；或者被作为一种特定的排序算法来使用。

例3．2b是实现归并排序算法的一个例子，你可以将它和本章结尾的有关代码一起编译成一个可执行程序。有关list_t类型及其操作函数的代码也已在本章末尾列出。 

在例3．2b中，字符串被存放在一个链表中，而不是一个数组中。实际上，将数据组织为链表后更利于归并排序算法对其进行处理，因为数组中的元素是无法合并的，除非利用另外分配的内存空间。

例3．2b通过以下4个函数共同实现归并排序算法：

(1)split()函数 

split()函数将一个字符串链表分割为一个由多个字符串链表组成的链表，其中每一个字符串链表都已经是排好序的。例如，如果初始链表为("the" "quick""brown" "fox")，则split()函数将返回一个由3个链表组成的链表，这3个链表分别为(“the”)，("quick”)和("brown”“fox”)。因为字符串“brown”和“fox”已经是排好序的，所以它们被放到一个链表中。

尽管split()函数将初始链表分割为一系列只含一个数据的链表后，本例的排序算法仍然能很好地执行，但是，如果初始链表中的数据已经接近有序，那么在分割初始链表时，将相邻的有序数据放到同一个链表中，就能大大减少以后的工作量，从而使本例的排序算法成为自然的排序算法(见本章开始部分中的介绍)。

当输入链表不为空时，程序第14—24行的循环将一直进行下去。在每次循环中，程序第16行将构造一个新的链表；第17—22行将把输入链表中的元素不断地移到所构造的链表之中，直到处理完输入链表中的所有元素，或者检查到两个无序的元素；第23行将把所构造的链表添加到输出链表(它的数据也是链表)中。

(2)merge()函数

merge()函数将两个数据已经有序的链表合并为一个数据有序的链表。

当正在合并的两个链表都不为空时，程序第37—45行的循环将一直进行下去。第40行的if 语句将比较两个链表中的第一个元素，并把较小的元素移到输出链表中。当正在合并的两个链表中有一个为空时，另一个链表中的元素必须全部添加到输出链表中。第46行和第47行将已为空的链表和另一个链表与输出链表链接上，从而结束整个合并过程。

(3)mergePairs()函数

通过调用merge()函数，mergePairs()函数分别对一个由字符串链表组成的链表中的每个对链表进行合并，并用合并所得的链表代替原来的那对链表。

当输入链表不为空时，程序第61—77行的循环将一直进行下去。第63行的if语句检查输入链表中是否至少有两个字符串链表，如果没有，第76行就把这个单独的链表添加到输出链表中；如果有，第65行和第66行将从输入链表中选出头两个链表，第68行和69行将合并这两个链表，第72行将把合并所得的链表添加到输出链表中，第70行、第71行和第73行将释放所分配的过渡性结点，第72行和第73行将从输入链表中删去头两个链表。

(4)sortStrings()函数

sonStrings()函数对一个字符串数组进行归并排序。

程序第88行和第89行将字符串数组转换为一个字符串链表。第90行调用split()函数将初始链表分割为一个由字符串链表组成的链表。第91行和第92行调用mereePairs()函数将分割所得的链表中的所有字符串链表合并为一个字符串链表。第93行检查合并所得的链表是否为空(当原来的字符串数组中只有。个元素时该链表为空)，若不为空，才能将该链表从分割所得的链表中移出。

需要注意的是，sortStrings()函数没有释放它所用过的内存。

例3．2b一个归并排序算法程序 

#include<stdlib.h>
#include "list.h"

/*
 * Splits a list of strings into a list of lists of strings
 * in which each list of strings is sorted.
 */
static list-t split(list_t in)
{
     list-t out
     list-t * curr;
     out. head=out, tail=NULL;

     while (in. head)
     {
          curr =newList();
          do
          {
               appendNode (curr, removeHead (&in));
          }
        while (in. head && strcmp (curr->tail->u. str,
                            in. head->u.str) < = 0);
        appendNode(&out, newNode(curr));
    }
    return Out;
}

/*
 * Merge two sorted lists into a third sorted list,
 *.which is then returned.
 */
static list_t merge (list_t first, list_t second)
{
        list_t out;
        out.head=out, tail=NULL;

        while (first. head && second, head)
          {
                listnode_t * temp;
                if (strcmp (first. head->u.str,
                       second. head->u.str) <=0)
                     appendNode(&out, removeHead(&first));
                 else
                      appendNode (&out, removeHead (&second));
          }
        concatList (&out, &first);
        concatList (&out, &second);
        return out;
}

/*
 * Takes a list of lists 0{ strings and merges'each pair of
 * lists into a single list. The resulting list has 1/2 as
 * many lists as the original.
 */
static list_t mergePairs(list_t in)
{
     list_ t out;
     out. head:out, tail=NUll;

     while (in. head)
     {
          if (in. head->next)
          {
                 list_t * first =in. head->u.list;
                 list_t * second;
                             in.head->next->u.list
                 in. head->u.list = copyOf (merge ( * first,
                                                          * second));
                 free (first);
                 free (second);
                 appendNode (&out, removeHead (&in))
                 free (removeHead (&in));
            }
            else
                appendNode (&out, removeHead (&in));
     }
     return out
}

/* Sort strings using merge sort */
void sortStrings (const char * array[])
{
        int i;
        list_t out;
        out.head=out, tail=NULL;

         for (i=0; array[i]; i++)
            appendNode(&out, newNode((void * ) array[i]))
         out= split (out);
        while (out.head ! =out.tail)
            out = mergePairs (out);
        if (out.head)
                 out = * out.head->u.list;
       for (i=O; array[i]; i++)
               array[i] = removeHead (&out)->u.str;
}