C語言實(shí)現(xiàn)單鏈表的快速排序算法
背景
傳統(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è)單向鏈表的排序。除此之外,為了簡(jiǎn)化將 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)行通過
測(cè)試案例
(1)一般數(shù)據(jù)樣例
(2)只有一個(gè)數(shù)據(jù)時(shí)
(2)有重復(fù)數(shù)據(jù)時(shí)
總結(jié)
到此這篇關(guān)于C語言實(shí)現(xiàn)單鏈表的快速排序算法的文章就介紹到這了,更多相關(guān)C語言快速排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c++指針參數(shù)傳遞和引用參數(shù)傳遞的區(qū)別解析
這篇文章主要介紹了c++指針參數(shù)傳遞和引用參數(shù)傳遞的區(qū)別解析,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-07-07關(guān)于統(tǒng)計(jì)數(shù)字問題的算法
本文介紹了統(tǒng)計(jì)數(shù)字問題的算法,計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0,1,2,3,.....9,并有每一步的解題思路,需要的朋友可以參考下2015-08-08C語言關(guān)于自定義數(shù)據(jù)類型之枚舉和聯(lián)合體詳解
枚舉顧名思義就是把所有的可能性列舉出來,像一個(gè)星期分為七天我們就可以使用枚舉,聯(lián)合體是由關(guān)鍵字union和標(biāo)簽定義的,和枚舉是一樣的定義方式,不一樣的是,一個(gè)聯(lián)合體只有一塊內(nèi)存空間,什么意思呢,就相當(dāng)于只開辟最大的變量的內(nèi)存,其他的變量都在那個(gè)變量占據(jù)空間2021-11-11