C语言单向链表快速排序算法设计与实现

设计思路

单向链表不支持像数组那样的索引访问，因此不能简单使用双指针从两端向中间收缩。本算法的核心思想是保留“分治”策略：以第一个节点为枢轴（Pivot），遍历剩余节点，将其重新分配到两个新链表 less 和 more 中：

• less 链表：包含所有键值小于枢轴的节点。
• more 链表：包含所有键值大于或等于枢轴的节点。

为了减少频繁的内存分配与指针断开操作，算法需要记录两个子链表的头节点和尾节点指针。在单次遍历结束后，分别对 less 和 more 链表递归执行排序，最后将排序好的子链表拼接回枢轴节点两侧，形成完整的有序链表。

算法主要步骤

第1步：初始化分区指针

设定 listHead 指向当前待排序链表的首节点，作为枢轴。listTail 用于接收该层递归结束后的新尾节点位置。设置 lessHead, lessTail, moreHead, moreTail 均为空（NULL）。
令 current 指向 listHead->next，即准备从第二个节点开始遍历。

第2步：逐一遍历并分流节点

当 current 不为空时，循环比较 current->key 与枢轴 listHead->key：

若 current->key 小于枢轴值：
1. 若 lessHead 为空，说明 current 是 less 链表首个节点，赋值给 lessHead。
2. 否则，将当前 lessTail 的下一个节点指向 current。
3. 更新 lessTail = current。

若 current->key 大于或等于枢轴值：
同理，将节点追加到 more 链表尾部，并更新 moreHead 和 moreTail。

第3步：收尾处理与递归链接

遍历结束后，需切断子链表的尾部以防止成环：

• 若 moreTail 存在，置 moreTail->next = NULL。
• 若 lessTail 存在，置 lessTail->next = NULL。

随后处理枢轴节点的连接：

1. 递归处理 more 部分：如果 moreHead 不为空，递归调用快排函数，并将结果链接到枢轴后面（listHead->next = moreHead）；若为空，则枢轴本身即为尾部，更新 *listTail = *listHead 并置后继为空。

2. 递归处理 less 部分：如果 lessHead 不为空，递归调用快排函数。将排序后的 less 链表尾部指向枢轴（lessTail->next = listHead），并更新新的头部 *listHead = lessHead；若为空，则枢轴即为头部。

快速排序算法实现

以下是核心递归函数的 C 语言实现。注意指针参数的使用方式，以便在函数内部修改外部头尾指针。

Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, moreHead = NULL, moreTail = NULL;
	current = (*listHead)->next;
	if ((*listHead)->next != NULL) // 只有当链表节点数大于1时才需划分
	{
		for (current = (*listHead)->next; current; current = current->next)
		{
			if (current->key < (*listHead)->key)
			{
				if (lessHead == NULL)
					lessHead = current;
				else
					lessTail->next = current;
				lessTail = current;
			}
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}
		}
		// 截断子链表尾部
		if (moreTail) moreTail->next = NULL;
		if (lessTail) lessTail->next = NULL;

		// 处理 more 链表及其与枢轴的连接
		if (moreHead != NULL)
		{
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}

		// 处理 less 链表及其与枢轴的连接
		if (lessHead != NULL)
		{
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		else
		{
			lessHead = *listHead;
		}
		return lessHead;
	}
	else
		return *listHead;
}

完整程序结构与测试验证

为了验证算法，程序包含了辅助函数用于创建链表、获取尾指针以及打印输出。以下是在 Visual Studio 2017 环境下通过编译测试的完整源代码：

#include<stdio.h>
#include<malloc.h>
typedef struct Lnode
{
	int key;
	struct Lnode* next;
}Lnode, *Linklist;

Linklist createList(Linklist L, int n)
{
	L = (Linklist)malloc(sizeof(Lnode));
	L->next = NULL;
	Lnode *p, *r;
	r = L;
	p = (Lnode*)malloc(sizeof(Lnode));
	scanf("%d", &r->key);
	for (int i = 1; i < n; i++)
	{
		p = (Lnode*)malloc(sizeof(Lnode));
		scanf("%d", &p->key);
		r->next = p;
		r = p;
	}
	r->next = NULL;
	return L;
}

Linklist getTail(Linklist L)
{
	while (L->next)
		L = L->next;
	return L;
}

void Print(Linklist L)
{
	Lnode *p;
	p = L;
	while (p)
	{
		printf("%d ", p->key);
		p = p->next;
	}
}

// ... (此处省略上述 Quicksort 函数源码) ...

int main()
{
	Lnode* L = NULL;
	int n;
	printf("请输入元素个数\n");
	scanf("%d", &n);
	printf("请输入元素\n");
	L = createList(L, n);
	Lnode* listTail;
	listTail = getTail(L);
	Quicksort(&L, &listTail);
	printf("排序后元素序列为\n");
	Print(L);
	return 0;
}

以下为三种典型场景的运行截图验证：

1. 常规数据输入：输入一组无序整数，链表被正确重排为升序。

2. 仅含一个数据：满足递归出口条件，直接返回原节点。

3. 包含重复数据：根据算法定义，等于枢轴值的节点归入 more 侧，仍能保持稳定性输出。

总结

通过维护子链表的头尾指针，我们成功解决了单向链表在传统快排中缺乏双向遍历能力的问题。相比冒泡排序等 O(n²) 算法，此方法在大多数情况下能将平均时间复杂度降低至 O(n log n)。需要注意的是，极端情况下（如链表已有序且枢轴选取不当）可能退化为 O(n²)，实际工程中可结合随机选取枢轴来优化性能。以上就是C语言实现单链表的快速排序算法的详细内容，更多关于C语言单链表排序优化的资料请关注本站其它相关文章！