算法--归并排序（链表）

归并排序

http://blog.csdn.net/morewindows/article/details/6678165

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作：

http://www.tuicool.com/articles/iy2QRn6

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如：设有数列 [6，202，100，301，38，8，1]

初始状态：6, 202, 100, 301, 38, 8, 1

第一次归并后：[6, 202], [100, 301], [8, 38], [1]，比较次数：3；

第二次归并后：[6, 100, 202, 301]，[1, 8, 38]，比较次数：4；

第三次归并后：[1, 6, 8, 38, 100, 202, 301]，比较次数：4；

归并排序是在归并的操作基础上采用分治法的排序方法；（归并 + 分治）

归并操作就是将两个有序的子列合并成一个有序总列，

分治法就是通过二分法将序列不断分成子列。

个人理解

与快速排序方法相同的是，两者都采用分治方法，即将一个大规模的问题，分解成两个小规模的问题，然后对每个小规模问题，做递归运算。

与快速排序不同的是，快速排序只有分治过程，分治过程中就行行筛选（实现部分排序），

归并排序，分治过程，就是很单纯，只有分的动作，然后归并排序，有一个合并的过程，合并过程执行了排序工功能。

这两种方式是两种截然不同的整理杂物的模式：

1、快速排序，精髓体现在筛选，一分二，一大一小。

例如杂物太多了，不好按个的大小排序处理，先初步按照大小初步分分类。

2、归并排序，精髓体现在合并，物品按照相邻位置，两个元素为一组，两个元素合并为一个。

杂物不多，两两归一，成为有序的一个列。然后列列合并为一个更大的有序列。

归并排序，既可以使用递归方式实现，也可以采用堆栈工具实现。

递归方式比较容易理解，示意代码：

void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }  
}

堆栈方法可以克服递归方法带来的缺点，递归方法由于深层的递归调用，会耗费大量内存，如果带合并数目巨大，则可能耗费完栈的资源。

同时递归方法，有利于数组形式写法，数组写法的代码参考（http://blog.csdn.net/morewindows/article/details/6678165），

堆栈方法，更加适合链表，因为递归方法，是按照数组元素的下标（数组的索引）分治和归并的，如果对于链表实现，则需要二外的链表节点位置计算的开销。

C程序实现

链表方式实现此算法（merge sort）参考：

https://github.com/fanqingsong/code-snippet/blob/master/C/MergeSort/mergesortList.c

归并操作：

PT_LIST_LINKNODE Merge_TwoList(PT_LIST_LINKNODE ptLinkNode_one, PT_LIST_LINKNODE ptLinkNode_two)
{
    PT_NODE_LISTHEAD ptNodeListHead_one = NULL;
    PT_NODE_LISTHEAD ptNodeListHead_two = NULL;
    PT_NODE_LISTHEAD ptNodeListHead_merged = NULL;

    PT_LIST_LINKNODE ptListHead_One = NULL;
    PT_LIST_LINKNODE ptListHead_Two = NULL;
    PT_LIST_LINKNODE ptListHead_merged = NULL;
    
    PT_NODE ptNodeOne = NULL;
    PT_NODE ptNodeTwo = NULL;
    
    E_BOOL_TYPE bIsListOneGo = TRUE;
    E_BOOL_TYPE bIsListTwoGo = TRUE;

    PT_LIST_LINKNODE ptLinkNode_merged = NULL;

    ptNodeListHead_merged = GetNode_ListHead();
    if ( !ptNodeListHead_merged )
    {
        return NULL;
    }
    ptListHead_merged = &(ptNodeListHead_merged->tListHead);

    ptNodeListHead_one = list_entry(ptLinkNode_one, T_NODE_LISTHEAD, tLinkNode);
    ptNodeListHead_two = list_entry(ptLinkNode_two, T_NODE_LISTHEAD, tLinkNode);

    ptListHead_One = &(ptNodeListHead_one->tListHead);
    ptListHead_Two = &(ptNodeListHead_two->tListHead);

    // merge list one and list two into a new list
    ptNodeOne = List_DetachFirstNode(ptListHead_One);
    ptNodeTwo = List_DetachFirstNode(ptListHead_Two);
    while( ptNodeOne && ptNodeTwo )
    {
        // node one is smaller
        if ( strcmp(ptNodeOne->str, ptNodeTwo->str) < 0 )
        {
            List_AddNode2Tail(ptListHead_merged, ptNodeOne);

            ptNodeOne = NULL;

            // list one shall get next node, list two keep current node
            bIsListOneGo = TRUE;
            bIsListTwoGo = FALSE;
        }
        // node two is smaller or equal
        else
        {
            List_AddNode2Tail(ptListHead_merged, ptNodeTwo);

            ptNodeTwo = NULL;

            // list one shall keep current node, list two shall get next node
            bIsListOneGo = FALSE;
            bIsListTwoGo = TRUE;
        }

        if ( bIsListOneGo )
        {
            ptNodeOne = List_DetachFirstNode(ptListHead_One);
        }

        if ( bIsListTwoGo )
        {
            ptNodeTwo = List_DetachFirstNode(ptListHead_Two);
        }
    }

    if ( ptNodeOne )
    {
        List_AddNode2Tail(ptListHead_merged, ptNodeOne);
        ptNodeOne = NULL;
    }

    if ( ptNodeTwo )
    {
        List_AddNode2Tail(ptListHead_merged, ptNodeTwo);
        ptNodeTwo = NULL;
    }

    // if list one has node yet, add them to merge list
    ptNodeOne = List_DetachFirstNode(ptListHead_One);
    while( ptNodeOne )
    {
        List_AddNode2Tail(ptListHead_merged, ptNodeOne);

        ptNodeOne = List_DetachFirstNode(ptListHead_One);
    }

    // if list two has node yet, add them to merge list
    ptNodeTwo = List_DetachFirstNode(ptListHead_Two);
    while( ptNodeTwo )
    {
        List_AddNode2Tail(ptListHead_merged, ptNodeTwo);

        ptNodeTwo = List_DetachFirstNode(ptListHead_Two);
    }

    FreeNode_ListHead(&ptNodeListHead_one);
    FreeNode_ListHead(&ptNodeListHead_two);

    ptLinkNode_merged = &(ptNodeListHead_merged->tLinkNode);
    
    return ptLinkNode_merged;
}

对于链表的一趟归并：

// execute one merge process, from left stack to right stack
void Merge_OneTime(PT_LIST_LINKNODE ptStackSrc, PT_LIST_LINKNODE ptStackDest)
{
    // execute two way merge
    PT_LIST_LINKNODE ptLinkNode_one = NULL;
    PT_LIST_LINKNODE ptLinkNode_two = NULL;
    PT_LIST_LINKNODE ptLinkNode_merged = NULL;

    while( !IsStackEmpty(ptStackSrc) )
    {
        ptLinkNode_one = PopLinkNodeFromStack(ptStackSrc);
        ptLinkNode_two = PopLinkNodeFromStack(ptStackSrc);

        // src stack has only one list, add to destine stack
        if ( !ptLinkNode_two )
        {
            PushLinkNodeOnStack(ptStackDest, ptLinkNode_one);
            break;
        }

        //src stack has two list yet, merge it, add merged list to destine stack
        ptLinkNode_merged = Merge_TwoList(ptLinkNode_one, ptLinkNode_two);
        
        PushLinkNodeOnStack(ptStackDest, ptLinkNode_merged);
    }
}

归并排序core接口：

实现思路：

1、将list中每一个元素都转变为一个list，然后压入 leftStack

LIST: （1）->(2)->(3)

leftStack: (LIST:(1)) -> (LIST:(2))->(LIST:(3))

2、将leftStack中从栈顶开始，每两个元素（list）一组，进行合并，合并之后的list，压入rightStack

rightStack: (LIST:(1)) -> (LIST:(2)->(3))

3、按照2规则，将rightStack中链表，归并后，压入 leftStack。循环执行 2 3 ，直到栈中只有一个链表停止。此链表即为排序完成的链表。

leftStack: (LIST:(1)->(2)->(3))

void List_MergeSort(PT_LIST_LINKNODE ptListHead)
{
    // left stack for the even times of merging
    T_LIST_LINKNODE tStackLeft = {NULL, NULL};
    PT_LIST_LINKNODE ptStackLeft = &tStackLeft;

    // right stack for the odd times of merging    
    T_LIST_LINKNODE tStackRight = {NULL, NULL};
    PT_LIST_LINKNODE ptStackRight = &tStackRight;

    // final list may be in left stack or right stack, the final stack pointer is the result
    PT_LIST_LINKNODE ptStackFinal = NULL;

    PT_LIST_LINKNODE ptLinkNode_merged = NULL;
    PT_NODE_LISTHEAD ptNodeListHead_merged = NULL;
    PT_LIST_LINKNODE ptListHead_merged = NULL;

    INIT_LIST_HEAD(&tStackLeft);
    INIT_LIST_HEAD(&tStackRight);

    if ( IsListEmpty(ptListHead) )
    {
        return ;
    }

    MakeEveryNodeList2Stack(ptListHead, ptStackLeft);
    //PrintStackLists(ptStackLeft);

    while ( TRUE )
    {
        // merge the lists from left stack into right stack
        Merge_OneTime(ptStackLeft, ptStackRight);
        //PrintStackLists(ptStackLeft);
        //PrintStackLists(ptStackRight);        
        if ( HasStackOneList(ptStackRight) )
        {
            ptStackFinal = ptStackRight;
            break;
        }

        // merge the lists from right stack into left stack
        Merge_OneTime(ptStackRight, ptStackLeft);
        //PrintStackLists(ptStackLeft);
        //PrintStackLists(ptStackRight);     
        if ( HasStackOneList(ptStackLeft) )
        {
            ptStackFinal = ptStackLeft;
            break;
        }
    }

    // record merged final list into list head
    ptLinkNode_merged = PopLinkNodeFromStack(ptStackFinal);
    ptNodeListHead_merged = list_entry(ptLinkNode_merged, T_NODE_LISTHEAD, tLinkNode);
    ptListHead_merged = &(ptNodeListHead_merged->tListHead);

    List_ReplaceHead(ptListHead_merged, ptListHead);
    FreeNode_ListHead(&ptNodeListHead_merged);
}

将表中节点全部转换为子链表函数：

// make every node be a list and push the stack on stack
void MakeEveryNodeList2Stack(PT_LIST_LINKNODE ptListHead, PT_LIST_LINKNODE ptStack)
{
    PT_LIST_LINKNODE ptLinkNode = NULL;
    PT_LIST_LINKNODE ptNextCache = NULL;
    PT_NODE_LISTHEAD ptNodeListHead = NULL;

    // make all elements enter the left stack
    list_for_each_safe(ptListHead, ptLinkNode, ptNextCache)
    {
        // detatch this node from list
        list_del(ptLinkNode);

        ptNodeListHead = GetNode_ListHead();
        List_AddLink2Tail(&(ptNodeListHead->tListHead), ptLinkNode);

        // push new list on left stack 
        PushLinkNodeOnStack(ptStack, &(ptNodeListHead->tLinkNode));
    }
}

链表操作改进

由于宏定义linux api容易引起宏使用的混淆问题，同时这些宏都是一些短小语句的定义，按照linux系统链表的定义方法进行参考，

给出链表操作接口使用 inline 函数方式：

// initialize the head and tail of list head as self
static inline void INIT_LIST_HEAD(PT_LIST_LINKNODE ptListHead)
{
    ptListHead->next = ptListHead;
    ptListHead->prev = ptListHead;
}

// insert new link node between previous link node and next link node
static inline void _list_add(PT_LIST_LINKNODE ptNewLink,
                  PT_LIST_LINKNODE ptPrevLink,
                  PT_LIST_LINKNODE ptNextLink)
{
    // splice new link and next link
    ptNewLink->next = ptNextLink;
    ptNextLink->prev = ptNewLink;

    // splice new link and previous link
    ptNewLink->prev = ptPrevLink;
    ptPrevLink->next = ptNewLink;
}

// delete the specific link node from list
static inline void list_del(PT_LIST_LINKNODE ptLinkNode)
{
    ptLinkNode->prev->next = ptLinkNode->next;
    ptLinkNode->next->prev = ptLinkNode->prev;
    
    ptLinkNode->prev = NULL;
    ptLinkNode->next = NULL;
}

// add new list node to  list head
static inline void list_add_head(PT_LIST_LINKNODE ptListHead,  PT_LIST_LINKNODE ptListNewLink)
{
    PT_LIST_LINKNODE ptPrevLink = ptListHead;
    PT_LIST_LINKNODE ptNextLink = ptListHead->next;
    
    _list_add(ptListNewLink,  ptPrevLink, ptNextLink);
}


// add new list node to  list tail
static inline void list_add_tail(PT_LIST_LINKNODE ptListHead, PT_LIST_LINKNODE ptListNewLink)
{
    PT_LIST_LINKNODE ptPrevLink = ptListHead->prev;
    PT_LIST_LINKNODE ptNextLink = ptListHead;
    
    _list_add(ptListNewLink, ptPrevLink, ptNextLink);
}

算法--归并排序（链表）

归并排序

归并操作

归并排序 是在归并的操作基础上采用分治法的排序方法； （归并 + 分治）