C语言实现单链表的快速排序算法

时间：2022-09-01 09:26:18|栏目：C代码|点击：次

背景

传统QuickSort算法最大不足之处在于，由于其基于可索引存储结构设计(一般为数组或索引表)，因而无法用于链式存储结构，而链式存储结构的实际应用非常广泛，例如动态存储管理、动态优先级调度等等，故本文针对于单向链表，以QuickSort的分治策略为基础，提出一种可用于单向链表的快速排序算法。

设计思路

将单向链表的首节点作为枢轴节点，然后从单向链表首部的第二个节点开始，逐一遍历所有后续节点，并将这些已遍历节点的key与枢轴节点的key进行比较，根据比较结果，重新将这些节点链接为less和more两个单向链表，less中所包含节点的key均小于枢轴节点的 key；more中所包含节点的key均大于或等于枢轴节点的key。然后再对得到的两个单链表进行递归操作，将进行内部递归排序最后连接到枢轴上。同时为达到在每次划分后将规模更小的两个单向链表链接到枢轴节点上，必须记录各自的尾节点位置，即需要设置两个指向尾节点的指针。less链表的首节点指针设定为lessHead，尾节点指针设定为lessTail；more链表的首节点指针设定为 moreHead，尾节点指针设定为moreTail。当前正在遍历的节点指针设定为current。当单向链表遍历结束后，亦即完成了一趟划分，如此递归进行，便可完成整个单向链表的排序。除此之外，为了简化将 less和more单向链表链接到枢轴节点前、后部的过程，还需设定两个指向单向链表尾节点的指针 lessTail和moreTail。在递归过程中，得到的单链表的长度会依次减小，直到长度减小到一的时候即为递归出口。

算法主要步骤

步骤1：算法接收两个指针，其中listHead指向单向链表首节点，listTail为空指针，划分过程中，listTail将指向单向链表的尾节点，划分后用于链接less单向链表到枢轴节点前。
步骤2：如果单向链表listHead仅有一个节点，则说明已有序，本层递归结束，返回listHead。
步骤3：令lessHead、lessTail、moreHead和 moreTail为空，令current为listHead的next域，即单向链表的第二个节点。
步骤4：如果current节点为空，则转入步骤13。
步骤5：如果current节点的key小于枢轴节点(即listHead)的key，则current节点应链接到 less单向链表，转入步骤6；否则，current节点应链接到more单向链表，转入步骤9。
步骤6：修改lessTail指针使其指向current 节点。如果lessHead为空，则转入步骤7；否则转入步骤8。
步骤7：将less节点链接为单链表的首节点。
步骤8：将current节点链接为less单链表的尾结点；
步骤9：修改moreTail指针使其指向current 节点。如果moreHead为空，则转入步骤10；否则转入步骤11。
步骤10：将currnet节点链接为more单向链表的首节点。
步骤11：将currnet节点链接为more单向链表的尾节点。
步骤12：将current节点移动到单向链表的下一个节点。
步骤13：如果more单向链表不为空，则转入步骤14；否则转入步骤18。
步骤14：标记more单向链表的结束位置，即置moreTail的next域为空。
步骤15：递归调用本算法，继续划分more单向链表，传人moreHead和moreTail。步骤16将经过递归排序的more单向链表链接到枢轴节点后。
步骤17：修改listTail指针使其指向more— Tail，以便本层递归结束后供上层递归过程使用。
步骤18：由于more单向链表为空，则枢轴节点便是尾节点，即置listHead的next域为空。步骤19：修改listTail指针使其指向listHead。
步骤20：如果less单向链表不为空，则转入步骤21；否则转入步骤24。
步骤21：标记less单向链表的结束位置，即置lessTail的next域为空。
步骤22：递归调用本算法，继续划分less单向链表，传人lessHead和lessTail。步骤23将经过递归排序的less单向链表链接到枢轴节点前。
步骤24：由于less单向链表为空，则枢轴节点便是首节点，即置lessHead为listHead。
步骤25：本层递归结束，返回lessHead。
示意图如下：

在这里插入图片描述

快速排序算法实现

Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, *moreHead = NULL, *moreTail = NULL;
	current = (*listHead)->next;//每次取首节点为枢纽，current指向第二个节点用于遍历
	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;
			}//current结点key小于枢纽key时放入less链表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current结点key大于枢纽key时放入more链表
		}
		//根据枢纽结点将T链表分为less和more两个链表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//将more链表尾结点next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空，则current为more链表的尾结点，对more链表进行递归处理,将more链表接在枢纽节点后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead为空，则只有less链表(即结点key全小于枢纽)，将枢纽结点接在less节点后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空，对less链表进行递归处理，再将枢纽节点接在less链表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead为空，则枢纽结点作为首节点
		return lessHead;
	}
	else
		return *listHead;
}

整个程序源代码

#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;
	}
}
//遍历单链表
Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, *moreHead = NULL, *moreTail = NULL;
	current = (*listHead)->next;//每次取首节点为枢纽，current指向第二个节点用于遍历
	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;
			}//current结点key小于枢纽key时放入less链表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current结点key大于枢纽key时放入more链表
		}
		//根据枢纽结点将T链表分为less和more两个链表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//将more链表尾结点next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空，则current为more链表的尾结点，对more链表进行递归处理,将more链表接在枢纽节点后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead为空，则只有less链表(即结点key全小于枢纽)，将枢纽结点接在less节点后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空，对less链表进行递归处理，再将枢纽节点接在less链表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead为空，则枢纽结点作为首节点
		return lessHead;
	}
	else
		return *listHead;
}
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;
}

整个程序已在Visual Studio 2017上运行通过