`

单链表归并排序

 
阅读更多

 

单链表归并排序-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 <wangyuxxx@163.com> 
 * @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);
}
分享到:
评论

相关推荐

    用单链表和队列实现归并排序

    在标题“用单链表和队列实现归并排序”中,我们可以理解到这个实现是利用了链表和队列的数据结构。链表是一种线性数据结构,其中的元素在内存中不是顺序存储的,而是通过指针链接。队列则是一种先进先出(FIFO)的...

    用面向对象程序设计对单链表进行归并排序

    在本案例中,我们将利用面向对象的方法对单链表进行归并排序,这是一种高效的排序算法,尤其适用于大规模数据。归并排序采用分而治之的策略,将大问题分解为小问题,再逐个解决,最后合并结果。 1. **分而治之思想*...

    WW1.rar_C 单链表 排序_归并排序

    总结来说,"WW1.rar_C 单链表 排序_归并排序"是一个C语言实现的项目,目标是对两个单链表进行归并排序。通过理解单链表的结构和归并排序的原理,我们可以分析和学习`WW1.C`中的实现,从而掌握在链表环境下实现高效...

    VC++实现有序单链表归并实验源代码

    在归并排序中,大问题被分解为小问题,然后将解决小问题的结果合并,最终得到大问题的解。对于链表的归并排序,通常分为以下步骤: 1. **分割**:将链表分成两半。在链表的中间位置找到一个节点,将其前后两部分...

    单链表为存储结构, 实现二路归并排序的算法

    在这个场景中,我们使用单链表作为存储结构来实现二路归并排序,这与传统的数组或动态数组有所不同,链表允许我们在不移动元素的情况下调整顺序。 首先,我们要理解单链表的基本概念。单链表由一系列节点组成,每个...

    C语言数据结构 链表与归并排序实例详解

    本文将深入探讨两种关键的数据结构操作:链表和归并排序。首先,链表是一种非连续存储的数据结构,它的每个元素(节点)包含数据和指向下一个节点的引用。而归并排序是一种高效的排序算法,尤其适用于链表的排序,...

    归并排序,排序等算法,数据结构,快速排序,链表排序

    本主题将深入探讨四种常见的排序算法:归并排序、快速排序以及与链表相关的排序方法。 首先,我们来讨论归并排序(Merge Sort)。这是一种基于分治策略的排序算法。归并排序将大问题分解为小问题,然后逐步合并这些...

    数据库系统实现-两阶段多路归并排序算法的C实现

    两阶段多路归并排序算法是一种常用于数据库管理系统中的高效排序方法。本文将深入探讨这个算法,并结合C语言的实现来阐述其工作原理。 首先,我们要理解什么是归并排序。归并排序是一种基于分治思想的排序算法,它...

    [算法]快速排序,归并排序,堆排序的数组和单链表实现 数组和链表.pdf

    快速排序、归并排序、堆排序的数组和单链表实现 快速排序是一种常用的排序算法,它的时间复杂度为O(nlogn),是目前最快的排序算法之一。快速排序的基本思想是选择一个基准元素,然后将数组分成两个部分,一部分的...

    单链表的排序,c源代码

    ### 单链表排序C语言实现 #### 一、引言 在计算机科学中,链表是一种常用的数据结构,它由一系列节点组成,每个节点包含数据...对于更复杂的场景或者更大的数据量,可以考虑使用其他更高效的排序算法如归并排序等。

    用C写的单链表的值插入排序

    单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据以及指向下一个节点的指针。在计算机科学中,排序是处理数据的...当然,对于大规模数据,更推荐使用其他效率更高的排序算法,如归并排序或快速排序。

    单链表排序

    选择排序虽然易于理解和实现,但在实际应用中,尤其是在处理大量数据时,可能需要考虑更高效的排序方法,如归并排序或快速排序,这些算法虽然实现起来相对复杂,但能提供更好的性能。 ### 进一步探索 为了提高链表...

    [算法]快速排序,归并排序,堆排序的数组和单链表实现 (1) 数组和链表.pdf

    快速排序、归并排序、堆排序的数组和单链表实现 以下是对快速排序、归并排序、堆排序的数组和单链表实现的知识点摘要: 快速排序 快速排序是一种基于比较的排序算法,它的时间复杂度为O(nlogn)。快速排序的基本...

    单链表上的简单选择排序算法

    在计算机科学中,排序算法是数据结构领域的重要组成部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如...在实际应用中,通常会使用更高效的排序算法,如归并排序或快速排序,特别是在处理大量数据时。

    简单的单链表排序 —— 学生管理程序

    在链表排序中,我们通常采用两种主要的排序算法:插入排序和归并排序。这里我们将以简单的插入排序为例,介绍如何对单链表进行排序。 **插入排序**的基本思想是将未排序的元素逐个插入到已排序的部分,从而保持已...

    C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题  设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中...

    单链表实现从小到大排序

    在实际应用中,更高效的排序算法如快速排序或归并排序可能更适合链表。 在实际编程中,我们通常会在主函数(Main Function)中创建一个链表实例,插入一些随机或预定义的数据,然后调用`sort_list`方法对其进行排序...

    单链表的创建,排序,归并,插入删除定位和获得元素,计算元素个数,打印链表

    本篇文章将深入探讨单链表的创建、排序、归并、插入、删除、定位、获取元素、计算元素个数以及打印链表等操作。 **1. 创建单链表** 创建单链表通常从创建头节点开始,头节点不存储任何数据,仅用于链接其他节点。...

    数据结构实验报告(链表,栈,串,数组,邻接表,邻接矩阵,查找,归并排序和快速排序的实验代码)

    本实验报告主要涵盖了链表、栈、串、数组、邻接表、邻接矩阵、查找算法、归并排序和快速排序这九大主题,这些都是数据结构与算法学习中的基础和关键部分。 首先,链表是一种线性数据结构,它的每个元素(节点)包含...

Global site tag (gtag.js) - Google Analytics