C语言数据结构链表与归并排序实例详解_网络技术

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

发布时间 - 2026-01-10 22:31:14 点击率：次

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

归并排序适合于对链表进行原址排序，即只改变指针的连接方式，不交换链表结点的内容。

归并排序的基本思想是分治法：先把一个链表分割成只有一个节点的链表，然后按照一定顺序、自底向上合并相邻的两个链表。

只要保证各种大小的子链表是有序的，那么最后返回的链表就一定是有序的.

归并排序分为分割和合并两个子过程。分割是用递归的方法，把链表对半分割成两个子链表；合并是在递归返回（回朔）的时候，把两个有序链表合并成一个有序链表。

(注意：只有一个节点的链表一定是有序的)

这里sort过程就是分割过程；merge过程就是合并且排序的过程

说到分割链表，那么问题来了：链表不是随机访问的，我怎么知道分割点在哪里？一个宝贵的经验就是：维护两个指针，一快一慢。快指针每次后移两个单位，慢指针每次只移动一个单位。当快指针移动到tail或者最后一个有效节点时，慢指针就指向了中间的节点。

sort过程:

Node* sort (Node* beg)
{
  if(beg==tail || beg->next==tail) return beg;
  Node* a = beg; Node* b = beg->next;
  while(b!=tail && b->next != tail)
  {
    a = a->next; b = b->next->next;
  }
  b = a->next;  //the beginning of right part
  a->next = tail; //the end of left part
  return merge(sort(beg), sort(b));
}

把链表分割之后就要合并。merge操作传入的参数是两个有序链表，返回的是合并后的有序的链表。两个有序链表简单拼接之后不一定是有序的，需要对每一个元素重排。这个重排的过程是从两个链表各自最小（最大）元素开始，谁小（大）就把谁放到新的链表里。

Node* LinkedList<T>::merge(Node* a, Node* b)
{
	Node dummy = Node();
	Node* head = &dummy;
	// temp是正在合并的表的节点
	Node* temp = head;
	while(a!=tail && b!=tail) //逐个比较链表a和链表b的每个元素
	{
		if(a->data <= b->data)
		{
			// 如果a比b小, 那么当前结点的后继就是a
			temp->next = a;
			// 把当前节点移向后继
			temp = a;
			// a后移
			a = a->next;
		}
		else 
		{
			temp->next = b;
			temp = b; 
			b = b->next;
		}
		// 如果原表a已经排完,那么新表后面就放b的剩余元素
		// 否则仍然以a为标准和b进行比较
		temp->next = (a==tail) ? b : a;
	}
	return head->next;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C语言数据结构 # 链表与归并排序 # 数据结构链表 # 归并排序 # C语言非递归算法解决快速排序与归并排序产生的栈溢出 # C语言递归实现归并排序详解 # C语言实现各种排序算法实例代码(选择 # 冒泡 # 插入 # 归并 # 希尔 # 快排 # 堆排序 # 计数) # C语言排序方法(冒泡 # 选择 # 快速) # C语言分治法实现归并排序 # C语言中数据结构之链表归并排序实例代码 # C语言实现排序算法之归并排序详解 # c语言排序之归并排序(递归和非递归) # 链表 # 递归 # 只有一个 # 的是 # 后移 # 是在 # 来了 # 说到 # 是从 # 数据结构 # 希望能 # 就把 # 谢谢大家 # 先把 # 适合于 # 到新 # 移向 # 治法 # 我怎么 # strong

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：测试自己制作的网站有哪些,论文在网上检测安全吗，是自己在网

下一篇：swoole和workerman详细分析：哪个更易入门？

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：测试自己制作的网站有哪些,论文在网上检测安全吗，是自己在网

下一篇：swoole和workerman详细分析：哪个更易入门？

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

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