单链表归并排序

 

单链表归并排序－O(nlogn)

 

由 王宇 原创并发布：

• 代码采用Doxygen注释
• 在以下环境中编译运行通过：Linux Puppy Tahr 6.0.5 kernel 3.14.56 gcc 4.8.4

 

/**
 * @file link_list_sort.c
 *
 * @brief 单链表的归并排序，需要保证O(nlgn)
 *
 * 思路：采用二分法，和归并操作，
 * 及将单链平分成两组，归并操作后合并成一个链。采用递归，重复以上操作。
 *
 * @author WangYu <[e-mail]> 
 * @data   2016-09-27
 * @version 1.0
 */

#include<stdio.h>
#include<stdlib.h>

typedef struct LinkList_s {
    int               value; /// 值  
    struct LinkList_s *next; /// 单链的下一个节点

}LinkList_t;


/**
 * @brief 从单链表的中间分成 a, b 两组
 *
 * 思路：分别采用快慢步长，快步长是慢的两倍，当快步长到达链表尾部时，慢步长刚好在链表中间
 *
 * @param [in]  head 单链头 
 * @param [out] a组 b组
 * @retval 空
 */
void getMiddle(LinkList_t *head, LinkList_t **a, LinkList_t **b) {
    LinkList_t *fast = NULL;
    LinkList_t *slow  = NULL;
    LinkList_t *previous;
    
    if (head != NULL && head->next != NULL) {
        fast = head;
        slow  = head;

        while (slow != NULL && fast != NULL) {

            if (slow->next == NULL) {
                break; 
            }

            previous = slow;
            slow = slow->next; 


            if (fast->next != NULL) {
                fast = fast->next->next;

            } else {
                break; 
            }
        }

        previous->next = NULL;  // a组的最后一个节点的Next 为NULL；

        *a = head;
        *b = slow;
    }

}


/**
 * ＠breif 归并操作，并合并两组
 *
 * 将单链表在中间分成a b两组, 归并操作并合并后的链表:sortList
 *
 * 归并操作：
 *
 *  对比两个分组，将较小的先放入sortList
 *  将第一组剩余的放入sortList
 *  将第二组剩余的放入sortList
 *
 * @param [in]  a组 b组
 * @retval 返回合并后的链
 */
LinkList_t *mergeLinkList(LinkList_t *a, LinkList_t *b) {
    LinkList_t *sortList = NULL, *sortListHead = NULL;

    if ( a == NULL && b != NULL ) {
        return b; 

    } else if (a != NULL && b == NULL) {
        return a; 

    } else  if (a == NULL && b == NULL){
        return NULL; 
    }

    // 准备并备份排序好的链表头 
    if ( a->value < b->value ) {
        sortListHead = a;
        a = a->next;

    } else {
        sortListHead = b; 
        b = b->next;
    }

    sortList = sortListHead ;

    // 对比两组，将较小的先插入到sortList尾部
    while (a != NULL &&  b!= NULL) {
        if ( a->value < b->value ) {
            sortList->next = a; 
            a = a->next;

        } else {
            sortList->next = b; 
            b = b->next;
        }

        sortList = sortList->next;
    }

    // 将a组中剩余部分插入到sortList尾部
    while (a != NULL) {
        sortList->next = a;

        a = a->next;
        sortList = sortList->next;
    } 

    // 将b组中剩余部分插入到sortList尾部
    while (b != NULL) {
        sortList->next = b;

        b = b->next;
        sortList = sortList->next;
    } 

    return sortListHead;
}


/**
 * @breif 递归二分链表并排序
 * @param [in]  head 单链头 
 * @retval 返回排序后的链
 */
LinkList_t *sortLinkList(LinkList_t *head) {
    LinkList_t *leftLinkList, *rightLinkList;

    if (head == NULL) {
        return NULL; 

    } else if (head->next == NULL) {
        return head; 
    }
   
    getMiddle(head, &leftLinkList, &rightLinkList);

    leftLinkList = sortLinkList(leftLinkList);
    rightLinkList = sortLinkList(rightLinkList);

    return mergeLinkList(leftLinkList, rightLinkList);
}


/**
 * @breif 建立一个简单的单链表,用于测试排序
 * @retval 返回单链表
 */
LinkList_t *createLinkList() {
    int i;
    LinkList_t *head = NULL, *current = NULL, *previous = NULL;

    // 10 个元素,从大到小
    for (i = 10; i > 0; i--) {
        current = (LinkList_t*)malloc(sizeof(LinkList_t)); 

        if (current == NULL) {
            perror("Error: malloc \n"); 
        }

        current->value = i;
        current->next = NULL;
        
        if (head == NULL) {
            head = current; 
            previous = current;

        } else {
            previous->next = current;
            previous = current;
        }
    }

    return head;
}


int main(){
    LinkList_t *head = NULL;

    head = createLinkList();
    head = sortLinkList(head);
   
    while (head != NULL) {
        printf("%d\n", head->value); 
        head = head->next;
    }

    exit(0);
}