快捷導(dǎo)航

C語言實(shí)現(xiàn)單鏈表的快速排序算法

更新時(shí)間：2022年01月20日 09:52:20 作者：CUP-GYC

大家好，本篇文章主要講的是C語言實(shí)現(xiàn)單鏈表的快速排序算法，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下

背景

傳統(tǒng)QuickSort算法最大不足之處在于，由于其基于可索引存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)(一般為數(shù)組或索引表)，因而無法用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)際應(yīng)用非常廣泛，例如動(dòng)態(tài)存儲(chǔ)管理、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度等等，故本文針對(duì)于單向鏈表，以QuickSort的分治策略為基礎(chǔ)，提出一種可用于單向鏈表的快速排序算法。

設(shè)計(jì)思路

將單向鏈表的首節(jié)點(diǎn)作為樞軸節(jié)點(diǎn)，然后從單向鏈表首部的第二個(gè)節(jié)點(diǎn)開始，逐一遍歷所有后續(xù)節(jié)點(diǎn)，并將這些已遍歷節(jié)點(diǎn)的key與樞軸節(jié)點(diǎn)的key進(jìn)行比較，根據(jù)比較結(jié)果，重新將這些節(jié)點(diǎn)鏈接為less和more兩個(gè)單向鏈表，less中所包含節(jié)點(diǎn)的key均小于樞軸節(jié)點(diǎn)的 key；more中所包含節(jié)點(diǎn)的key均大于或等于樞軸節(jié)點(diǎn)的key。然后再對(duì)得到的兩個(gè)單鏈表進(jìn)行遞歸操作，將進(jìn)行內(nèi)部遞歸排序最后連接到樞軸上。同時(shí)為達(dá)到在每次劃分后將規(guī)模更小的兩個(gè)單向鏈表鏈接到樞軸節(jié)點(diǎn)上，必須記錄各自的尾節(jié)點(diǎn)位置，即需要設(shè)置兩個(gè)指向尾節(jié)點(diǎn)的指針。less鏈表的首節(jié)點(diǎn)指針設(shè)定為lessHead，尾節(jié)點(diǎn)指針設(shè)定為lessTail；more鏈表的首節(jié)點(diǎn)指針設(shè)定為 moreHead，尾節(jié)點(diǎn)指針設(shè)定為moreTail。當(dāng)前正在遍歷的節(jié)點(diǎn)指針設(shè)定為current。當(dāng)單向鏈表遍歷結(jié)束后，亦即完成了一趟劃分，如此遞歸進(jìn)行，便可完成整個(gè)單向鏈表的排序。除此之外，為了簡化將 less和more單向鏈表鏈接到樞軸節(jié)點(diǎn)前、后部的過程，還需設(shè)定兩個(gè)指向單向鏈表尾節(jié)點(diǎn)的指針 lessTail和moreTail。在遞歸過程中，得到的單鏈表的長度會(huì)依次減小，直到長度減小到一的時(shí)候即為遞歸出口。

算法主要步驟

步驟1：算法接收兩個(gè)指針，其中l(wèi)istHead指向單向鏈表首節(jié)點(diǎn)，listTail為空指針，劃分過程中，listTail將指向單向鏈表的尾節(jié)點(diǎn)，劃分后用于鏈接less單向鏈表到樞軸節(jié)點(diǎn)前。
步驟2：如果單向鏈表listHead僅有一個(gè)節(jié)點(diǎn)，則說明已有序，本層遞歸結(jié)束，返回listHead。
步驟3：令lessHead、lessTail、moreHead和 moreTail為空，令current為listHead的next域，即單向鏈表的第二個(gè)節(jié)點(diǎn)。
步驟4：如果current節(jié)點(diǎn)為空，則轉(zhuǎn)入步驟13。
步驟5：如果current節(jié)點(diǎn)的key小于樞軸節(jié)點(diǎn)(即listHead)的key，則current節(jié)點(diǎn)應(yīng)鏈接到 less單向鏈表，轉(zhuǎn)入步驟6；否則，current節(jié)點(diǎn)應(yīng)鏈接到more單向鏈表，轉(zhuǎn)入步驟9。
步驟6：修改lessTail指針使其指向current 節(jié)點(diǎn)。如果lessHead為空，則轉(zhuǎn)入步驟7；否則轉(zhuǎn)入步驟8。
步驟7：將less節(jié)點(diǎn)鏈接為單鏈表的首節(jié)點(diǎn)。
步驟8：將current節(jié)點(diǎn)鏈接為less單鏈表的尾結(jié)點(diǎn)；
步驟9：修改moreTail指針使其指向current 節(jié)點(diǎn)。如果moreHead為空，則轉(zhuǎn)入步驟10；否則轉(zhuǎn)入步驟11。
步驟10：將currnet節(jié)點(diǎn)鏈接為more單向鏈表的首節(jié)點(diǎn)。
步驟11：將currnet節(jié)點(diǎn)鏈接為more單向鏈表的尾節(jié)點(diǎn)。
步驟12：將current節(jié)點(diǎn)移動(dòng)到單向鏈表的下一個(gè)節(jié)點(diǎn)。
步驟13：如果more單向鏈表不為空，則轉(zhuǎn)入步驟14；否則轉(zhuǎn)入步驟18。
步驟14：標(biāo)記more單向鏈表的結(jié)束位置，即置moreTail的next域?yàn)榭铡?br />步驟15：遞歸調(diào)用本算法，繼續(xù)劃分more單向鏈表，傳人moreHead和moreTail。步驟16將經(jīng)過遞歸排序的more單向鏈表鏈接到樞軸節(jié)點(diǎn)后。
步驟17：修改listTail指針使其指向more— Tail，以便本層遞歸結(jié)束后供上層遞歸過程使用。
步驟18：由于more單向鏈表為空，則樞軸節(jié) 點(diǎn)便是尾節(jié)點(diǎn)，即置listHead的next域?yàn)榭铡?步驟19：修改listTail指針使其指向listHead。
步驟20：如果less單向鏈表不為空，則轉(zhuǎn)入步驟21；否則轉(zhuǎn)入步驟24。
步驟21：標(biāo)記less單向鏈表的結(jié)束位置，即置lessTail的next域?yàn)榭铡?br />步驟22：遞歸調(diào)用本算法，繼續(xù)劃分less單向鏈表，傳人lessHead和lessTail。步驟23將經(jīng)過遞歸排序的less單向鏈表鏈接到樞軸節(jié)點(diǎn)前。
步驟24：由于less單向鏈表為空，則樞軸節(jié) 點(diǎn)便是首節(jié)點(diǎn)，即置lessHead為listHead。
步驟25：本層遞歸結(jié)束，返回lessHead。
示意圖如下：

在這里插入圖片描述

快速排序算法實(shí)現(xiàn)

Linklist Quicksort(Linklist *listHead, Linklist *listTail)
{
	Lnode *current;
	Lnode* lessHead = NULL, *lessTail = NULL, *moreHead = NULL, *moreTail = NULL;
	current = (*listHead)->next;//每次取首節(jié)點(diǎn)為樞紐，current指向第二個(gè)節(jié)點(diǎn)用于遍歷
	if ((*listHead)->next != NULL)//當(dāng)鏈表節(jié)點(diǎn)數(shù)不為1時(shí)(說明鏈表未排好序)
	{
		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結(jié)點(diǎn)key小于樞紐key時(shí)放入less鏈表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current結(jié)點(diǎn)key大于樞紐key時(shí)放入more鏈表
		}
		//根據(jù)樞紐結(jié)點(diǎn)將T鏈表分為less和more兩個(gè)鏈表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//將more鏈表尾結(jié)點(diǎn)next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空，則current為more鏈表的尾結(jié)點(diǎn)，對(duì)more鏈表進(jìn)行遞歸處理,將more鏈表接在樞紐節(jié)點(diǎn)后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead為空，則只有l(wèi)ess鏈表(即結(jié)點(diǎn)key全小于樞紐)，將樞紐結(jié)點(diǎn)接在less節(jié)點(diǎn)后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空，對(duì)less鏈表進(jìn)行遞歸處理，再將樞紐節(jié)點(diǎn)接在less鏈表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead為空，則樞紐結(jié)點(diǎn)作為首節(jié)點(diǎn)
		return lessHead;
	}
	else
		return *listHead;
}

整個(gè)程序源代碼

#include<stdio.h>
#include<malloc.h> 
typedef struct Lnode
{
	int key;
	struct Lnode* next;
}Lnode, *Linklist;
//鏈表結(jié)構(gòu)體類型
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;
}
//初始初始化及尾插法（正序）創(chuàng)建單鏈表
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;//每次取首節(jié)點(diǎn)為樞紐，current指向第二個(gè)節(jié)點(diǎn)用于遍歷
	if ((*listHead)->next != NULL)//當(dāng)鏈表節(jié)點(diǎn)數(shù)不為1時(shí)(說明鏈表未排好序)
	{
		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結(jié)點(diǎn)key小于樞紐key時(shí)放入less鏈表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current結(jié)點(diǎn)key大于樞紐key時(shí)放入more鏈表
		}
		//根據(jù)樞紐結(jié)點(diǎn)將T鏈表分為less和more兩個(gè)鏈表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//將more鏈表尾結(jié)點(diǎn)next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空，則current為more鏈表的尾結(jié)點(diǎn)，對(duì)more鏈表進(jìn)行遞歸處理,將more鏈表接在樞紐節(jié)點(diǎn)后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead為空，則只有l(wèi)ess鏈表(即結(jié)點(diǎn)key全小于樞紐)，將樞紐結(jié)點(diǎn)接在less節(jié)點(diǎn)后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空，對(duì)less鏈表進(jìn)行遞歸處理，再將樞紐節(jié)點(diǎn)接在less鏈表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead為空，則樞紐結(jié)點(diǎn)作為首節(jié)點(diǎn)
		return lessHead;
	}
	else
		return *listHead;
}
int main()
{
	Lnode* L = NULL;
	int n;
	printf("請(qǐng)輸入元素個(gè)數(shù)\n");
	scanf("%d", &n);
	printf("請(qǐng)輸入元素\n");
	L = createList(L, n);
	Lnode* listTail;
	listTail = getTail(L);
	Quicksort(&L, &listTail);
	printf("排序后元素序列為\n");
	Print(L);
	return 0;
}

整個(gè)程序已在Visual Studio 2017上運(yùn)行通過