基于鏈表排序算法的綜述1

PAGE2015學(xué)年第一學(xué)期《算法分析與設(shè)計(jì)》大作業(yè)——鏈表排序綜述院系：軟件學(xué)院班級(jí)：軟件設(shè)計(jì)姓名：范**基于鏈表排序算法的綜述摘要：?jiǎn)捂湵硎且环N鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。排序時(shí)將一個(gè)任意的數(shù)據(jù)元素序列排列成一個(gè)有序的序列。單鏈表排序主要功能是對(duì)以鏈表為存儲(chǔ)結(jié)構(gòu)的數(shù)值型數(shù)據(jù)進(jìn)行排序，主要的排序方式有：冒泡排序，選擇排序，插入排序，快速排序，歸并排序以及基數(shù)排序。關(guān)鍵詞：?jiǎn)捂湵礞湵砼判虼鎯?chǔ)結(jié)構(gòu)引言：?jiǎn)捂湵砼判蚴菍⒁粋€(gè)以鏈表為存儲(chǔ)結(jié)構(gòu)的數(shù)值型任意序列，排列成一個(gè)方便于數(shù)據(jù)查詢的有序序列。1.需求分析選擇何種排序方法，要考慮的首要因素是關(guān)于文件的存儲(chǔ)結(jié)構(gòu)。文件存儲(chǔ)結(jié)構(gòu)有以下兩種：順序結(jié)構(gòu)：類似于線性表的順序存儲(chǔ)結(jié)構(gòu)，將文件存儲(chǔ)在一片連續(xù)的存儲(chǔ)空間，邏輯上相鄰的記錄在存儲(chǔ)器中的物理未知也是相鄰的，這種結(jié)構(gòu)上對(duì)文件排序一般要作記錄的移動(dòng)。當(dāng)發(fā)生成片記錄的移動(dòng)時(shí)，是一個(gè)很耗時(shí)間的工作；鏈表結(jié)構(gòu)：類似于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，文件中記錄用結(jié)點(diǎn)來表示，其物理位置任意，結(jié)點(diǎn)之間用指針相連，鏈表結(jié)構(gòu)的結(jié)點(diǎn)在于排序是無需移動(dòng)記錄，只需修改相應(yīng)記錄的指針即可；2．?dāng)?shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)2.1鏈表鏈表中的數(shù)據(jù)是以節(jié)點(diǎn)來表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。以“結(jié)點(diǎn)的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i2.1.1單鏈表1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（LinkedList）。鏈表的具體存儲(chǔ)表示為：①用一組任意的存儲(chǔ)單元來存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的）②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)┌───┬───┐│data│next│└───┴───┘data域--存放結(jié)點(diǎn)值的數(shù)據(jù)域next域--存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）注意：①鏈表通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（SingleLinkedList）?！纠烤€性表（bat，cat，eat，fat，hat，jat，lat，mat）的單鏈表示如示意圖3、頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即NULL。4、單鏈表的一般圖示法由于我們常常只注重結(jié)點(diǎn)間的邏輯順序，不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際位置，可以用箭頭來表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。5、單鏈表類型描述typedefcharDataType;//假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符typedefstructnode{//結(jié)點(diǎn)類型定義DataTypedata;//結(jié)點(diǎn)的數(shù)據(jù)域structnode*next;//結(jié)點(diǎn)的指針域}ListNode;typedefListNode*LinkList;ListNode*p;LinkListhead;注意：①LinkList和ListNode是不同名字的同一個(gè)指針類型（命名的不同是為了概念上更明確）②*LinkList類型的指針變量head表示它是單鏈表的頭指針③ListNode類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針6、指針變量和結(jié)點(diǎn)變量指針變量結(jié)點(diǎn)變量定義在變量說明部分顯式定義在程序執(zhí)行時(shí)，通過標(biāo)準(zhǔn)函數(shù)malloc生成取值非空時(shí)，存放某類型結(jié)點(diǎn)實(shí)際存放結(jié)點(diǎn)各域內(nèi)容的地址操作方式通過指針變量名訪問通過指針生成、訪問和釋放①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode*)malloc(sizeof(ListNode))；//函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p)；//釋放p所指的結(jié)點(diǎn)變量空間③結(jié)點(diǎn)分量的訪問利用結(jié)點(diǎn)變量的名字*p訪問結(jié)點(diǎn)分量方法一：(*p).data和(*p).next方法二：p-﹥data和p-﹥next④指針變量p和結(jié)點(diǎn)變量*p的關(guān)系指針變量p的值——結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p的值——結(jié)點(diǎn)內(nèi)容(*p).data的值——p指針?biāo)附Y(jié)點(diǎn)的data域的值(*p).next的值——*p后繼結(jié)點(diǎn)的地址*((*p).next)——*p后繼結(jié)點(diǎn)注意：①若指針變量p的值為空（NULL），則它不指向任何結(jié)點(diǎn)。此時(shí)，若通過*p來訪問結(jié)點(diǎn)就意味著訪問一個(gè)不存在的變量，從而引起程序的錯(cuò)誤。②有關(guān)指針類型的意義和說明方式的詳細(xì)解釋可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。2單鏈表的建立\o"編輯本段"編輯鏈表操作中動(dòng)態(tài)存儲(chǔ)分配要使用標(biāo)準(zhǔn)函數(shù)，先介紹一下這些函數(shù)。(1)malloc(size)在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)一個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間。(2)calloc(n，size)在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)n個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間，函數(shù)返回值為分配空間的首地址。若此函數(shù)未被成功執(zhí)行，函數(shù)返回值為0。(3)free(p)釋放由指針p所指向的存儲(chǔ)單元，而存儲(chǔ)單元的大小是最近一次調(diào)用malloc()或calloc()函數(shù)時(shí)所申請(qǐng)的存儲(chǔ)空間。在頭文件\"stdlib．h”中包含了這些函數(shù)的信息，使用這些函數(shù)時(shí)需在程序開頭用文件包含指令#include“stdlib．h”指明。另請(qǐng)讀者注意，調(diào)用動(dòng)態(tài)存儲(chǔ)分配函數(shù)返回的指針是指向void類型或char類型的指針，在具體使用時(shí)，要根據(jù)所指向的數(shù)據(jù)進(jìn)行強(qiáng)制類型轉(zhuǎn)換。2.1.2單鏈表的建立有頭插法、尾插法兩種方法1．頭插法單鏈表是用戶不斷申請(qǐng)存儲(chǔ)單元和改變鏈接關(guān)系而得到的一種特殊數(shù)據(jù)結(jié)構(gòu)，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結(jié)點(diǎn)。由于鏈表的長(zhǎng)度是隨機(jī)的，故用一個(gè)while循環(huán)來控制鏈表中結(jié)點(diǎn)個(gè)數(shù)。假設(shè)每個(gè)結(jié)點(diǎn)的值都大于O，則循環(huán)條件為輸入的值大于o。申請(qǐng)存儲(chǔ)空間可使用malloc()函數(shù)實(shí)現(xiàn)，需設(shè)立一申請(qǐng)單元指針，但malloc()函數(shù)得到的指針并不是指向結(jié)構(gòu)體的指針，需使用強(qiáng)制類型轉(zhuǎn)換，將其轉(zhuǎn)換成結(jié)構(gòu)體型指針。剛開始時(shí)，鏈表還沒建立，是一空鏈表，head指針為NULL。鏈表建立的過程是申請(qǐng)空間、得到數(shù)據(jù)、建立鏈接的循環(huán)處理過程。2.尾插法若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時(shí)，頭指針固定不動(dòng)，故必須設(shè)立一個(gè)搜索指針，向鏈表右邊延伸，則整個(gè)算法中應(yīng)設(shè)立三個(gè)鏈表指針，即頭指針head、搜索指針p2、申請(qǐng)單元指針pl。尾插法最先得到的是頭結(jié)點(diǎn)。2.2排序排序本身并不是討論數(shù)據(jù)結(jié)構(gòu)類型，而是建立在數(shù)據(jù)結(jié)構(gòu)上的一種運(yùn)算。其功能是將一個(gè)無需的記錄序列調(diào)整成有序的序列。2.2.1排序的定義設(shè)含有n個(gè)記錄（R）的文件f=(R1,R2,R3……Rn),相應(yīng)記錄關(guān)鍵字的集合K={k1,k2,k3……kn},若對(duì)1,2……n的一種排序：P1P2……Pn(1<=Pi<=n,i!=j時(shí)，Pi！=Pj)有：Kp1<=kp2……<=kpn遞增關(guān)系或kp1>=kp2>=……>=kpn遞減關(guān)系則使文件f按key線性有序：（Rp1,Rp2……Rpn）稱這種運(yùn)算為排序2.2.2排序的方法根據(jù)各種排序思路，排序可以分為下面幾種：冒泡排序選擇排序插入排序快速排序歸并排序基數(shù)排序幾種排序的性能比較如下：3.算法分析3.1冒泡排序冒泡排序時(shí)一種簡(jiǎn)單的交換類排序算法，它通過對(duì)相鄰元素的交換，逐步將待排序列變成有序序列。其算法的主要思想是：反復(fù)掃描排序記錄序列，在掃描過程中順次比較相鄰的兩個(gè)元素的大小，若逆序就交換位置。3.1.1冒泡排序在單鏈表上的實(shí)現(xiàn)功能：冒泡排序(由小到大)

返回：指向鏈表表頭的指針

==========================

直接插入排序的基本思想就是對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點(diǎn)，自上而下對(duì)相鄰的兩個(gè)節(jié)點(diǎn)依次進(jìn)行比較和調(diào)整，讓鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num為鍵值）較大的節(jié)點(diǎn)往下沉，鍵值較小的往上冒。即：每當(dāng)兩相鄰的節(jié)點(diǎn)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。

單向鏈表的冒泡排序圖示：

>[1]>[3]>[2]...>[n]>[NULL]（原鏈表）

head1->next3->next2->nextn->next>[1]>[2]>[3]...>[n]>[NULL]（排序后鏈表）

head1->next2->next3->nextn->next圖14：有N個(gè)節(jié)點(diǎn)的鏈表冒泡排序任意兩個(gè)相鄰節(jié)點(diǎn)p、q位置互換圖示:

假設(shè)p1->next指向p，那么顯然p1->next->next就指向q,

p1->next->next->next就指向q的后繼節(jié)點(diǎn)，我們用p2保存

p1->next->next指針。即：p2=p1->next->next，則有：

[]>[p]>[q]>[]（排序前）

p1->nextp1->next->nextp2->next

圖15[]>[q]>[p]>[]（排序后）圖161、排序后q節(jié)點(diǎn)指向p節(jié)點(diǎn)，在調(diào)整指向之前，我們要保存原p的指向節(jié)點(diǎn)地址，即：p2=p1->next->next；

2、順著這一步一步往下推,排序后圖16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;

3、在圖15中p2->next原是q發(fā)出來的指向，排序后圖16中q的指向要變?yōu)橹赶騪的，而原來p1->next是指向p的，所以p2->next=p1->next;

4、在圖15中p1->next原是指向p的，排序后圖16中p1->next要指向q,原來p1->next->next（即p2)是指向q的，所以p1->next=p2;

5、至此，我們完成了相鄰兩節(jié)點(diǎn)的順序交換。對(duì)于鏈表每一個(gè)結(jié)點(diǎn)看成豎著排序的“氣泡”，然后分別從頭結(jié)點(diǎn)向尾結(jié)點(diǎn)掃描。在掃描的過程中時(shí)刻注意兩個(gè)相鄰元素的順序，保證前一結(jié)點(diǎn)元素的數(shù)據(jù)域小于后一結(jié)點(diǎn)元素的數(shù)據(jù)域，這樣經(jīng)過一趟的掃描后就使較大的元素沉到鏈表的尾部，然后記住鏈表尾結(jié)點(diǎn)的位置，下次又從頭結(jié)點(diǎn)向后掃描，由于在前一地址，所以這次掃描最大的元素不再參加排序，將剩下的元素進(jìn)行排序，排序的過程中保證使得后一結(jié)點(diǎn)元素的數(shù)據(jù)域大于前一結(jié)點(diǎn)元素的數(shù)據(jù)域。這樣反復(fù)掃描，并不斷縮小排序的空間，直到整個(gè)序列有序?yàn)橹埂?.1.2代碼實(shí)現(xiàn)在排序中，只需記住最后的排好序的元素的位置即可，定義的鏈?zhǔn)浇Y(jié)構(gòu)和具體設(shè)計(jì)如下：Voidbubblesort(linklist*head)//單鏈表上的冒泡排序算法{Linklist*end,*p,*q;//end用來記錄排好序的最后一個(gè)結(jié)點(diǎn)的地址P,q,保持前驅(qū)和后繼的關(guān)系Elemtypetemp;P=head->next;Q=p->next;End=NULL;//排序前end指向列尾NULLWhile(end!=head->next//如果head所指結(jié)點(diǎn)的next成員為end，則結(jié)束循環(huán){P=head->next;//p結(jié)點(diǎn)總是從鏈表的頭結(jié)點(diǎn)開始Q=p->next;//q總是指向p所指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)While(p->next!=end)//當(dāng)p->next的值為end時(shí)，表示已到鏈尾{If(p->data->q->data)//按照數(shù)據(jù)域從小到大排序{temp=p->data;q->data=temp;q->data=temp;}P=q;Q=p->next;}End=p;}}//使end指向每次排序后的q所指的結(jié)點(diǎn)即尾結(jié)點(diǎn)3.2選擇排序?qū)τ谝粋€(gè)給定的數(shù)據(jù)序列，要對(duì)這個(gè)序列進(jìn)行排序（從小到大或從大到?。紫葎?chuàng)建鏈表，將待排序序列存放于此鏈表中，由于我們考慮的是交換數(shù)據(jù)所在的節(jié)點(diǎn)，所以在需要交換兩個(gè)節(jié)點(diǎn)時(shí)本質(zhì)上是交換鏈表中的兩個(gè)節(jié)點(diǎn)，由于在鏈表中沒有像數(shù)組中那利用下標(biāo)隨機(jī)的訪問元素的機(jī)制，所以需要用一個(gè)指針從頭到尾進(jìn)行掃描，以這樣的方式來訪問每一個(gè)節(jié)點(diǎn)。選擇排序是最符合人們思維習(xí)慣的一種排序方法。排序的基本思路為：每次從待排文件中挑選一個(gè)key值最小的記錄放置于它應(yīng)所在的位置，若待排文件長(zhǎng)度為M，則選擇n-1次便達(dá)到排序的目的。3.2.1排序方法設(shè)待排文件f=(R1R2……Rn),相應(yīng)內(nèi)集合k={k1,k2……kn},首先進(jìn)行n-1次key比較，選擇一個(gè)最小的kj(1<j<n),將R1與Rj互換，于是最小key記錄落在了R1的位置，接著在余下的（R2，R3……Rn）中選出key次小者，放置于R2位置，依此類推，當(dāng)待選記錄中只剩下一個(gè)記錄時(shí)，排序完畢。我認(rèn)為寫鏈表這類程序，關(guān)鍵是理解：

head存儲(chǔ)的是第一個(gè)節(jié)點(diǎn)的地址，head->next存儲(chǔ)的是第二個(gè)節(jié)點(diǎn)的地址；

任意一個(gè)節(jié)點(diǎn)p的地址，只能通過它前一個(gè)節(jié)點(diǎn)的next來求得。單向鏈表的選擇排序圖示：

>[1]>[3]>[2]...>[n]>[NULL]（原鏈表）

head1->next3->next2->nextn->next>[NULL]（空鏈表）

firsttail>[1]>[2]>[3]...>[n]>[NULL]（排序后鏈表）

first1->next2->next3->nexttail->next圖10：有N個(gè)節(jié)點(diǎn)的鏈表選擇排序先在原鏈表中找最小的，找到一個(gè)后就把它放到另一個(gè)空的鏈表中；2、空鏈表中安放第一個(gè)進(jìn)來的節(jié)點(diǎn)，產(chǎn)生一個(gè)有序鏈表,并且讓它在原鏈表中分離出來（此時(shí)要注意原鏈表中出來的是第一個(gè)節(jié)點(diǎn)還是中間其它節(jié)點(diǎn)）；3、繼續(xù)在原鏈表中找下一個(gè)最小的，找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針；3.2.2代碼實(shí)現(xiàn)LinkListSelectSort(LinkListL){LinkListfirst;/*排列后有序鏈的表頭指針*/LinkListtail;/*排列后有序鏈的表尾指針*/LinkListp_min;/*保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針*/LinkListmin;/*存儲(chǔ)最小節(jié)點(diǎn)*/LinkListp;/*當(dāng)前比較的節(jié)點(diǎn)*/first=NULL;while(L!=NULL)/*在鏈表中找鍵值最小的節(jié)點(diǎn)。*/{/*注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方*/for(p=L,min=L;p->next!=NULL;p=p->next)/*循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn)。*/{if(p->next->data<min->data)/*找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn)。*/{p_min=p;/*保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p。*/min=p->next;}}/*保存鍵值更小的節(jié)點(diǎn)。*//*上面for語(yǔ)句結(jié)束后，就要做兩件事；一是把它放入有序鏈表中；二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表。*//*第一件事*/if(first==NULL)/*如果有序鏈表目前還是一個(gè)空鏈表*/{first=min;/*第一次找到鍵值最小的節(jié)點(diǎn)。*/tail=min;}/*注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn)。*/else/*有序鏈表中已經(jīng)有節(jié)點(diǎn)*/{tail->next=min;/*把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它。*/tail=min;}/*尾指針也要指向它。*//*第二件事*/if(min==L)/*如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)*/{//printf("表頭%d已經(jīng)是最小，當(dāng)前結(jié)點(diǎn)后移。\n",min->data);L=L->next;}/*顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK*/Else/*如果不是第一個(gè)節(jié)點(diǎn)*/{p_min->next=min->next;}}/*前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表。*/if(first!=NULL)/*循環(huán)結(jié)束得到有序鏈表first*/{tail->next=NULL;}/*單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL*/L=first;returnL;}3.3插入排序3.3.1插入排序定義直接插入排序的基本思想就是假設(shè)鏈表的前面n-1個(gè)節(jié)點(diǎn)是已經(jīng)按鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num為鍵值）排好序的，對(duì)于節(jié)點(diǎn)n在這個(gè)序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次對(duì)鏈表從頭到尾執(zhí)行一遍，就可以使無序鏈表變?yōu)橛行蜴湵怼?/p>

3.3.2插入排序的方法設(shè)待排序文件f=(R1,R2……Rn),對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)為單鏈表結(jié)構(gòu)，如圖所示：鏈表插入排序?qū)嶋H上市一個(gè)對(duì)鏈表遍歷的過程。先將子表置為空表，然后一次掃描鏈表中的每個(gè)結(jié)點(diǎn)，設(shè)其指針為P，搜素到P結(jié)點(diǎn)在當(dāng)前子表的適當(dāng)未知，將其插入。假設(shè)含有4個(gè)記錄的鏈表如圖所示：其中記錄用key代替，排序過程如下：（1）初始，如圖所示：（2）插入50，當(dāng)前子表為空，p結(jié)點(diǎn)為子表的第一個(gè)結(jié)點(diǎn)插入，如圖所示：（3）插入36，因36<50，故當(dāng)前p結(jié)點(diǎn)插在50之前，如圖所示：（4）插入66,66大于子表中的所有key，故當(dāng)前key，應(yīng)掛在表尾，如圖所示：（5）插入12,12<36,將其插入36之前，如圖所示：?jiǎn)蜗蜴湵淼闹苯硬迦肱判驁D示：

>[1]>[3]>[2]...>[n]>[NULL]（原鏈表）

head1->next3->next2->nextn->next>[1]>[NULL]（從原鏈表中取第1個(gè)節(jié)點(diǎn)作為只有一個(gè)節(jié)點(diǎn)的有序鏈表）

head

圖11>[3]>[2]...>[n]>[NULL]（原鏈表剩下用于直接插入排序的節(jié)點(diǎn)）

first3->next2->nextn->next

圖12>[1]>[2]>[3]...>[n]>[NULL]（排序后鏈表）

head1->next2->next3->nextn->next圖13：有N個(gè)節(jié)點(diǎn)的鏈表直接插入排序1、先在原鏈表中以第一個(gè)節(jié)點(diǎn)為一個(gè)有序鏈表，其余節(jié)點(diǎn)為待定節(jié)點(diǎn)。

2、從圖12鏈表中取節(jié)點(diǎn)，到圖11鏈表中定位插入。

3、上面圖示雖說畫了兩條鏈表，其實(shí)只有一條鏈表。在排序中，實(shí)質(zhì)只增加了一個(gè)用于指向剩下需要排序節(jié)點(diǎn)的頭指針first罷了。

這一點(diǎn)請(qǐng)讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。

*/3.3.3代碼實(shí)現(xiàn)structstudent*InsertSort(structstudent*head)

{structstudent*first;/*為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針*/

structstudent*t;/*臨時(shí)指針變量：插入節(jié)點(diǎn)*/

structstudent*p;/*臨時(shí)指針變量*/

structstudent*q;/*臨時(shí)指針變量*/

first=head->next;/*原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來理解。*/

head->next=NULL;/*只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11來理解。*/while(first!=NULL)/*遍歷剩下無序的鏈表*/

{/*注意：這里for語(yǔ)句就是體現(xiàn)直接插入排序思想的地方*/

for(t=first,q=head;((q!=NULL)&&(q->num<t->num));p=q,q=q->next);/*無序節(jié)點(diǎn)在有序鏈表中找插入的位置*/

/*退出for循環(huán)，就是找到了插入的位置*/

/*注意：按道理來說，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了。*/

first=first->next;/*無序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中。*/

if(q==head)/*插在第一個(gè)節(jié)點(diǎn)之前*/

{head=t;}else/*p是q的前驅(qū)*/

{p->next=t;}t->next=q;/*完成插入動(dòng)作*/

/*first=first->next;*/}

returnhead;}3.4快速排序3.4.1快速排序的思想單鏈表的快排序和數(shù)組的快排序基本思想相同，同樣是基于劃分，但是又有很大的不同：?jiǎn)捂湵聿恢С只谙聵?biāo)的訪問。故書中把待排序的鏈表拆分為2個(gè)子鏈表。為了簡(jiǎn)單起見，選擇鏈表的第一個(gè)節(jié)點(diǎn)作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點(diǎn)放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對(duì)待排序鏈表掃描一遍之后，左邊子鏈表的節(jié)點(diǎn)值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個(gè)子鏈表的橋梁。然后分別對(duì)左、右兩個(gè)子鏈表進(jìn)行遞歸快速排序，以提高性能。

但是，由于單鏈表不能像數(shù)組那樣隨機(jī)存儲(chǔ)，和數(shù)組的快排序相比較，還是有一些需要注意的細(xì)節(jié)：

1、支點(diǎn)的選取，由于不能隨機(jī)訪問第K個(gè)元素，因此每次選擇支點(diǎn)時(shí)可以取待排序那部分鏈表的頭指針。

2、遍歷量表方式，由于不能從單鏈表的末尾向前遍歷，因此使用兩個(gè)指針分別向前向后遍歷的策略實(shí)效，

事實(shí)上，可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。3.4.2快速排序的方法方法一：具體方法為：

1)定義兩個(gè)指針pslow，pfast，其中pslow指向單鏈表的頭結(jié)點(diǎn)，pfast指向單鏈表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn);

2)使用pfast遍歷單鏈表，每遇到一個(gè)比支點(diǎn)小的元素，就令pslow=pslow->next，然后和pslow進(jìn)行數(shù)據(jù)交換。

3、交換數(shù)據(jù)方式，直接交換鏈表數(shù)據(jù)指針指向的部分，不必交換鏈表節(jié)點(diǎn)本身。方法二：選擇鏈表的第一個(gè)節(jié)點(diǎn)作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點(diǎn)放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對(duì)待排序鏈表掃描一遍之后，左面子鏈表的節(jié)點(diǎn)值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個(gè)子鏈表的橋梁。然后根據(jù)左、右子鏈表中節(jié)點(diǎn)數(shù)，選擇較小的進(jìn)行遞歸快速排序，而對(duì)數(shù)目較多的則進(jìn)行迭代排序。3.4.3快速排序的代碼Structnode*night;//右邊子鏈表的第一個(gè)節(jié)點(diǎn)Structnode**left_walk,**night_walk;//作為指針，把其指向的節(jié)點(diǎn)加入到相應(yīng)的子鏈表中Structnode*pivot,*old;//pivot為基準(zhǔn)，old為循環(huán)整個(gè)排序鏈表的指針For(old=(*head)->next;old!=end;old=old->next){If(old->data<pivot->data){//小于基準(zhǔn)，加入到左面的子鏈表，繼續(xù)比較++left_count;*left_walk=old;//把該節(jié)點(diǎn)加入到左邊的鏈表中；Left_walk=&(old->next);}else{//大于基準(zhǔn)，加入到右邊的子鏈表，繼續(xù)比較++right_count;*right_count;*right_walk=old;Right_walk=&(old->next);}}3.5歸并排序3.5.1歸并排序的定義歸并排序（Mergesort）是創(chuàng)建在歸并操作上的一種有效的\o"排序"排序\o"算法"算法。該算法是采用\o"分治法"分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用。歸并操作的過程如下：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置重復(fù)步驟3直到某一指針到達(dá)序列尾將另一序列剩下的所有元素直接復(fù)制到合并序列尾3.5.2算法基本思路

設(shè)兩個(gè)有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個(gè)局部的暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回R[low..high]中。

（1）合并過程

合并過程中，設(shè)置i，j和p三個(gè)指針，其初值分別指向這三個(gè)記錄區(qū)的起始位置。合并時(shí)依次比較R[i]和R[j]的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1[p]中，然后將被復(fù)制記錄的指針i或j加1，以及指向復(fù)制位置的指針p加1。

重復(fù)這一過程直至兩個(gè)輸入的子文件有一個(gè)已全部復(fù)制完畢(不妨稱其為空)，此時(shí)將另一非空的子文件中剩余記錄依次復(fù)制到R1中即可。

（2）動(dòng)態(tài)申請(qǐng)R1

實(shí)現(xiàn)時(shí)，R1是動(dòng)態(tài)申請(qǐng)的，因?yàn)樯暾?qǐng)的空間可能很大，故須加入申請(qǐng)空間是否成功的處理。

3.5.3歸并算法

voidMerge(SeqListR，intlow，intm，inthigh)

{//將兩個(gè)有序的子文件R[low..m)和R[m+1..high]歸并成一個(gè)有序的

//子文件R[low..high]

inti=low，j=m+1，p=0；//置初始值

RecType*R1；//R1是局部向量，若p定義為此類型指針?biāo)俣雀?/p>

R1=(ReeType*)malloc((high-low+1)*sizeof(RecType))；

if(!R1)//申請(qǐng)空間失敗

Error("Insufficientmemoryavailable!")；

while(i<=m&&j<=high)//兩子文件非空時(shí)取其小者輸出到R1[p]上

R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；

while(i<=m)//若第1個(gè)子文件非空，則復(fù)制剩余記錄到R1中

R1[p++]=R[i++]；

while(j<=high)//若第2個(gè)子文件非空，則復(fù)制剩余記錄到R1中

R1[p++]=R[j++]；

for(p=0，i=low；i<=high；p++，i++)

R[i]=R1[p]；//歸并完成后將結(jié)果復(fù)制回R[low..high]

}//Merge歸并排序有兩種實(shí)現(xiàn)方法：自底向上和自頂向下。

1、自底向上的方法

（1）自底向上的基本思想

自底向上的基本思想是：第1趟歸并排序時(shí)，將待排序的文件R[1..n]看作是n個(gè)長(zhǎng)度為1的有序子文件，將這些子文件兩兩歸并，若n為偶數(shù)，則得到個(gè)長(zhǎng)度為2的有序子文件；若n為奇數(shù)，則最后一個(gè)子文件輪空(不參與歸并)。故本趟歸并完成后，前個(gè)有序子文件長(zhǎng)度為2，但最后一個(gè)子文件長(zhǎng)度仍為1；第2趟歸并則是將第1趟歸并所得到的個(gè)有序的子文件兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序文件為止。

上述的每次歸并操作，均是將兩個(gè)有序的子文件合并成一個(gè)有序的子文件，故稱其為"二路歸并排序"。類似地有k(k>2)路歸并排序。

（2）二路歸并排序的全過程(略)

（3）一趟歸并算法分析：

在某趟歸并中，設(shè)各子文件長(zhǎng)度為length(最后一個(gè)子文件的長(zhǎng)度可能小于length)，則歸并前R[1..n]中共有個(gè)有序的子文件：R[1..length]，R[length+1..2length]，…，。

注意：

調(diào)用歸并操作將相鄰的一對(duì)子文件進(jìn)行歸并時(shí)，必須對(duì)子文件的個(gè)數(shù)可能是奇數(shù)、以及最后一個(gè)子文件的長(zhǎng)度小于length這兩種特殊情況進(jìn)行特殊處理：

①若子文件個(gè)數(shù)為奇數(shù)，則最后一個(gè)子文件無須和其它子文件歸并(即本趟輪空)；

②若子文件個(gè)數(shù)為偶數(shù)，則要注意最后一對(duì)子文件中后一子文件的區(qū)間上界是n。

具體算法如下：

voidMergePass(SeqListR，intlength)

{//對(duì)R[1..n]做一趟歸并排序

inti；

for(i=1;i+2*length-1<=n;i=i+2*length)

Merge(R，i，i+length-1，i+2*length-1)；

//歸并長(zhǎng)度為length的兩個(gè)相鄰子文件

if(i+length-1<n)//尚有兩個(gè)子文件，其中后一個(gè)長(zhǎng)度小于length

Merge(R，i，i+length-1，n)；//歸并最后兩個(gè)子文件

//注意：若i≤n且i+length-1≥n時(shí)，則剩余一個(gè)子文件輪空，無須歸并

}//MergePass

（4）二路歸并排序算法

voidMergeSort(SeqListR)

{//采用自底向上的方法，對(duì)R[1..n]進(jìn)行二路歸并排序

intlength；

for(1ength=1；length<n；length*=2)//做趟歸并

MergePass(R，length)；//有序段長(zhǎng)度≥n時(shí)終止

}

注意：

自底向上的歸并排序算法雖然效率較高，但可讀性較差。2、自頂向下的方法

采用分治法進(jìn)行自頂向下的算法設(shè)計(jì)，形式更為簡(jiǎn)潔。

（1）分治法的三個(gè)步驟

設(shè)歸并排序的當(dāng)前區(qū)間是R[low..high]，分治法的三個(gè)步驟是：

①分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)

②求解：遞歸地對(duì)兩個(gè)子區(qū)間R[low..mid]和R[mid+1..high]進(jìn)行歸并排序；

③組合：將已排序的兩個(gè)子區(qū)間R[low..mid]和R[mid+1..high]歸并為一個(gè)有序的區(qū)間R[low..high]。

遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1（一個(gè)記錄自然有序）。

（2）具體算法

voidMergeSortDC(SeqListR，intlow，inthigh)

{//用分治法對(duì)R[low..high]進(jìn)行二路歸并排序

intmid；

if(low<high){//區(qū)間長(zhǎng)度大于1

mid=(low+high)/2；//分解

MergeSortDC(R，low，mid);//遞歸地對(duì)R[low..mid]排序

MergeSortDC(R，mid+1，high)；//遞歸地對(duì)R[mid+1..high]排序

Merge(R，low，mid，high)；//組合，將兩個(gè)有序區(qū)歸并為一個(gè)有序區(qū)

}

}//MergeSortDC

（3）算法MergeSortDC的執(zhí)行過程(略)

算法MergeSortDC的執(zhí)行過程如下圖所示歸樹。

3.5.4歸并排序的算法分析

1、穩(wěn)定性

歸并排序是一種穩(wěn)定的排序。

2、存儲(chǔ)結(jié)構(gòu)要求

可用順序存儲(chǔ)結(jié)構(gòu)。也易于在鏈表上實(shí)現(xiàn)。

3、時(shí)間復(fù)雜度

對(duì)長(zhǎng)度為n的文件，需進(jìn)行趟二路歸并，每趟歸并的時(shí)間為O(n)，故其時(shí)間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

4、空間復(fù)雜度

需要一個(gè)輔助向量來暫存兩有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為O(n)，顯然它不是就地排序。

注意：

若用單鏈表做存儲(chǔ)結(jié)構(gòu)，很容易給出就地的歸并排序3.6基數(shù)排序3.6.1基數(shù)排序的定義基數(shù)排序又稱桶排序或數(shù)字排序：按待排序記錄的關(guān)鍵字的組成成分進(jìn)行排序?；鶖?shù)排序和前面的各種內(nèi)部排序方法完全不同，不需要進(jìn)行關(guān)鍵字的比較和記錄的移動(dòng)。借助于多關(guān)鍵字排序思想實(shí)現(xiàn)單邏輯關(guān)鍵字的排序。鏈?zhǔn)交鶖?shù)排序：若記錄的關(guān)鍵字由若干確定的部分組成，每一位都有確定的數(shù)目的取值。對(duì)這樣的記錄序列排序的有效方法是基數(shù)排序。設(shè)有n個(gè)待排序記錄{R1，R2……Rn},關(guān)鍵字是由d位組成，每位有r種取值，則關(guān)鍵字R[i].key可以看成一個(gè)d元組：R[i].key={ki1.ki2……kid}基數(shù)排序可以采用前面介紹的MSD或LSD方法3.6.2基數(shù)排序的算法思想（1）首先以靜態(tài)鏈接存儲(chǔ)n個(gè)待排序記錄，頭結(jié)點(diǎn)指針指向第一個(gè)記錄結(jié)點(diǎn)；（2）一趟排序的步驟：a.分配：按kd值得升序順序，改變記錄指針，將鏈表中的記錄結(jié)點(diǎn)分配到r個(gè)鏈表中飯，每個(gè)鏈表中所有記錄的關(guān)鍵字的最低位的值都相等。b.收集：改變所有非空鏈表的尾結(jié)點(diǎn)指針，使其指向下一個(gè)非空鏈表的第一個(gè)結(jié)點(diǎn)，從而鏈表中的記錄重新鏈接成一個(gè)鏈表。（3）如此依次按kd-1,kd-2,……k1分別進(jìn)行d趟排序后結(jié)束。4.運(yùn)行環(huán)境在此次試驗(yàn)設(shè)計(jì)中，使用的運(yùn)行環(huán)境是Visualc++6.0。Visualc++6.0是microsoft公司推出的目前使用最廣泛的基于windows平臺(tái)的可視化編程環(huán)境，是在以往版本不斷更新的基礎(chǔ)上形成的，由于其功能強(qiáng)大，靈活性好，因而在各種c++語(yǔ)言開發(fā)工具中脫穎而出，成為目前最為流行的c++語(yǔ)言集成開發(fā)環(huán)境。5.結(jié)束語(yǔ)在這次的試驗(yàn)里，主要使用了各種排序的方法，對(duì)基于單鏈表的幾種排序有了一定的理解和學(xué)習(xí)。在今后的學(xué)習(xí)中，我將會(huì)對(duì)我的算法知識(shí)進(jìn)行進(jìn)一步的加深和學(xué)習(xí)。希望對(duì)算法思想能有更好的理解和認(rèn)識(shí)！參考文獻(xiàn)[1]譚浩強(qiáng)C++程序設(shè)計(jì)清華大學(xué)出版社2008.5.19—277[2]嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社2008.3.1-17[3]徐緒松數(shù)據(jù)結(jié)構(gòu)與算法導(dǎo)論電子工業(yè)出版社2005[4]蘇世華數(shù)據(jù)結(jié)構(gòu)與算法解析國(guó)防工業(yè)出版社2005[5]寧正元算法與數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社2004[6]高小兵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程清華大學(xué)出版社2005[7]ThomasH.Cormen算法導(dǎo)論機(jī)械工業(yè)出版社2012.12[8]唐峻C/C++常用算法手冊(cè)中國(guó)鐵道出版社2014.06[9]鄒恒明算法之道機(jī)械工業(yè)出版社2012.04[10]戴艷零基礎(chǔ)學(xué)算法機(jī)械工業(yè)出版社2013.04附加代碼：/************************************************************************//*用單鏈表實(shí)現(xiàn)冒泡排序，輸入為0-9的數(shù)字字符*//************************************************************************/#include<stdio.h>#include<stdlib.h>#definePRprintf//定義一個(gè)單鏈表結(jié)構(gòu)體typedefstructnode{ longdata; structnode*next;}lklist;//快速排序，小的數(shù)據(jù)往前排，后的數(shù)據(jù)往后排lklist*sort(lklist*head){ if(head==NULL) returnNULL;lklist*p=head->next;lklist*p_pre=p;boolflag=false;//用于標(biāo)記是否有交換，當(dāng)數(shù)組有序的時(shí)候，提高判斷效率 while(p_pre->next!=NULL){longtemp=p_pre->data;p=p->next;while(p){if(temp<=(p->data)){p=p->next; continue;}else{longtemp_change;temp_change=p->data;p->data=p_pre->data;p_pre->data=temp_change;p=p->next;flag=true;}if(flag==false){returnhead;} } p_pre=p_pre->next;p=p_pre;}returnhead; }//向含有一個(gè)頭節(jié)點(diǎn)的單鏈表中插入數(shù)據(jù)lklist*create_lklist(lklist*head){PR("pleaseinputthenumberofthedataandendwithq(Q):\n"); while(1){charch[2];scanf("%s",ch);if(ch[0]=='q'||ch[0]=='Q')//輸入為q(Q)時(shí)停止輸入break;else{longintData=strtol(ch,0,10);lklist*temp=NULL; temp=(lklist*)malloc(sizeof(structnode));temp->data=intData;temp->next=NULL; temp->next=head->next; head->next=temp;}}returnhead;}//打印單鏈表中的數(shù)據(jù)信息voidprintf_lklist(lklist*head){if(NULL==head){return;}lklist*p=head->next;PR("thesortednumberis:\n");while(p){ PR("%d",p->data);p=p->next;} PR("\n");}//釋放有數(shù)據(jù)的鏈表中的節(jié)點(diǎn)voidfree_lklist(lklist*head){if(NULL==head){return;}lklist*p=head->next;lklist*pre;while(p){pre=p;p=p->next;free(pre);}}voidmain(){lklist*head=(structnode*)malloc(sizeof(structnode));head->next=NULL;//頭節(jié)點(diǎn)不存放數(shù)據(jù) head=create_lklist(head); head=sort(head); printf_lklist(head); free_lklist(head);free(head);//釋放申請(qǐng)的頭節(jié)點(diǎn)}運(yùn)行結(jié)果：pleaseinputthenumberofthedataandendwithq(Q):987564231qthesortednumberis:123456789Pressanykeytocontinue選擇排序#include"stdio.h"#include"stdlib.h"#include"time.h"#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatus;/*Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等*/typedefintElemType;/*ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int*/typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstructNode*LinkList;/*定義LinkList*/Statusvisit(ElemTypec){ printf("->%d",c); returnOK;}/*初始化順序線性表*/StatusInitList(LinkList*L){ *L=(LinkList)malloc(sizeof(Node));/*產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn)*/ if(!(*L))/*存儲(chǔ)分配失敗*/ returnERROR; (*L)->next=NULL;/*指針域?yàn)榭?/ returnOK;}/*初始條件：順序線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)*/intListLength(LinkListL){ inti=0; LinkListp=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*/ while(p) { i++; p=p->next; } returni;}/*初始條件：順序線性表L已存在*//*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素輸出*/StatusListTraverse(LinkListL){ LinkListp=L->next; while(p) { visit(p->data); p=p->next; } printf("\n"); returnOK;}/*隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L（尾插法）*/voidCreateListTail(LinkList*L,intn){ LinkListp,r; inti; srand(time(0));/*初始化隨機(jī)數(shù)種子*/ *L=(LinkList)malloc(sizeof(Node));/*L為整個(gè)線性表*/ r=*L;/*r為指向尾部的結(jié)點(diǎn)*/ for(i=0;i<n;i++) { p=(Node*)malloc(sizeof(Node));/*生成新結(jié)點(diǎn)*/ p->data=rand()%100+1;/*隨機(jī)生成100以內(nèi)的數(shù)字*/ r->next=p;/*將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)*/ r=p;/*將當(dāng)前的新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn)*/ } r->next=NULL;/*表示當(dāng)前鏈表結(jié)束*/}LinkListSelectSort2(LinkListL){ LinkListp,q,small; inttemp; for(p=L->next;p->next!=NULL;p=p->next) { small=p; for(q=p->next;q;q=q->next) { if(q->data<small->data) { small=q; } } printf("循環(huán)后，獲得最小值為:%d,此時(shí)鏈表為:",small->data); if(small!=p) { temp=p->data; p->data=small->data; small->data=temp; } ListTraverse(L); } printf("輸出排序后的數(shù)字:\n"); returnL;}LinkListSelectSort(LinkListL){ LinkListfirst;/*排列后有序鏈的表頭指針*/ LinkListtail;/*排列后有序鏈的表尾指針*/ LinkListp_min;/*保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針*/ LinkListmin;/*存儲(chǔ)最小節(jié)點(diǎn)*/ LinkListp;/*當(dāng)前比較的節(jié)點(diǎn)*/ first=NULL; while(L!=NULL)/*在鏈表中找鍵值最小的節(jié)點(diǎn)。*/ { /*注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方*/ for(p=L,min=L;p->next!=NULL;p=p->next)/*循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn)。*/ { if(p->next->data<min->data)/*找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn)。*/ { p_min=p;/*保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p。*/ min=p->next;/*保存鍵值更小的節(jié)點(diǎn)。*/ } } /*上面for語(yǔ)句結(jié)束后，就要做兩件事； 一是把它放入有序鏈表中； 二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表。*/ /*第一件事*/ if(first==NULL)/*如果有序鏈表目前還是一個(gè)空鏈表*/ { first=min;/*第一次找到鍵值最小的節(jié)點(diǎn)。*/ tail=min;/*注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn)。*/ } else/*有序鏈表中已經(jīng)有節(jié)點(diǎn)*/ { tail->next=min;/*把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它。*/ tail=min;/*尾指針也要指向它。*/ } /*第二件事*/ if(min==L)/*如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn)*/ { //printf("表頭%d已經(jīng)是最小，當(dāng)前結(jié)點(diǎn)后移。\n",min->data); L=L->next;/*顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK*/ } else/*如果不是第一個(gè)節(jié)點(diǎn)*/ { p_min->next=min->next;/*前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表。*/ } } if(first!=NULL)/*循環(huán)結(jié)束得到有序鏈表first*/ { tail->next=NULL;/*單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL*/ } L=first; returnL;}intmain(){ LinkListL; Statusi; charopp; ElemTypee; intfind; inttmp; i=InitList(&L); printf("初始化L后：ListLength(L)=%d\n",ListLength(L)); printf("\n1.查看鏈表\n2.創(chuàng)建鏈表（尾插法）\n3.鏈表長(zhǎng)度\n4.交換兩個(gè)結(jié)點(diǎn)\n0.退出\n請(qǐng)選擇你的操作：\n"); while(opp!='0') { scanf("%c",&opp); switch(opp) { case'1': ListTraverse(L); printf("\n"); break; case'2': CreateListTail(&L,10); printf("整體創(chuàng)建L的元素(尾插法)：\n"); ListTraverse(L); printf("\n"); break; case'3': //clearList(pHead);//清空鏈表 printf("ListLength(L)=%d\n",ListLength(L)); printf("\n"); break; case'4': L=SelectSort2(L); //printf("%d\n",find); ListTraverse(L); printf("\n"); break; case'0': exit(0); } }}運(yùn)行結(jié)果：快速排序：/**

**單鏈表的快速排序

**author:liuzhiwei

**date:2011-08-07

**/

#include<iostream>

#include<ctime>

usingnamespacestd;

//單鏈表節(jié)點(diǎn)

structSList

{

intdata;

structSList*next;

};

voidbulid_slist(SList**phead,intn)//指向指針的指針

{

inti;

SList*ptr=*phead;

for(i=0;i<n;++i)

{

SList*temp=newSList;

temp->data=rand()%n;//產(chǎn)生n個(gè)n以內(nèi)的隨機(jī)數(shù)

temp->next=NULL;

if(ptr==NULL)

{

*phead=temp;

ptr=temp;

}

else

{

ptr->next=temp;

ptr=ptr->next;

}

}

}

voidprint_slist(SList*phead)//輸出鏈表

{

SList*ptr=phead;

while(ptr)

{

printf("%d",ptr->data);

ptr=ptr->next;

}

printf("\n");

}

voidmy_swap(int*a,int*b)

{

inttemp;

temp=*a;

*a=*b;

*b=temp;

}

voidsort_slist(SList*phead,SList*pend)//將頭指針為phead，尾指針為pend的鏈表進(jìn)行排序

{

if(phead==NULL)

return;

if(phead==pend)

return;

SList*pslow=phead;

SList*pfast=phead->next;

SList*ptemp=phead;

while(pfast!=pend)

{

if(pfast->data<phead->data)//每次都選擇待排序鏈表的頭結(jié)點(diǎn)作為劃分的基準(zhǔn)

{

ptemp=pslow;//ptemp始終為pslow的前驅(qū)結(jié)點(diǎn)

pslow=pslow->next;

my_swap(&pslow->data,&pfast->data);//pslow指針指向比基準(zhǔn)小的結(jié)點(diǎn)組成的鏈表

}

pfast=pfast->next;

}

my_swap(&pslow->data,&phead->data);//此時(shí)pslow指針指向比基準(zhǔn)小的結(jié)點(diǎn)組成的鏈表的最后一個(gè)結(jié)點(diǎn)，也就是基準(zhǔn)的位置，所以要與基準(zhǔn)（head結(jié)點(diǎn)）交換

sort_slist(phead,pslow);//ptemp為左右兩部分分割點(diǎn)（基準(zhǔn)）的前一個(gè)結(jié)點(diǎn)

sort_slist(pslow->next,NULL);//右部分是比基準(zhǔn)大的結(jié)點(diǎn)組成的鏈表

}

voiddestroy_slist(SList*phead)

{

SList*ptr=phead;

while(ptr)

{

SList*temp=ptr;

ptr=ptr->next;

deletetemp;

}

}

intmain(void)

{

srand(time(NULL));

printf("Beforesortsinglelist\n");

SList*phead=NULL;

bulid_slist(&phead,100);

print_slist(phead);

printf("Aftersortsinglelist\n");

sort_slist(phead,NULL);

print_slist(phead);

destroy_slist(phead);

system("pause");

return0;

}運(yùn)行結(jié)果：Beforesortsinglelist59999765186176131646223529612449572249218697316937719931822084852819618460476028292662124639328745381342207536413052666376867128782799771916371109216643566347543198482254224485418883274823656Aftersortsinglelist12334467810121316161818192020212222242526272828282929303131313132323535363637383941414242444546474749495254565759606061616162636464656666697171717475767778828282848585868687889296979798999999請(qǐng)按任意鍵繼續(xù)...法2#include<stdio.h>

#include<stdlib.h>

#include<time.h>

//鏈表節(jié)點(diǎn)

structnode

{

intdata;

structnode*next;

};

//鏈表快排序函數(shù)

voidQListSort(structnode**head,structnode*h);

//打印鏈表

voidprint_list(structnode*head)

{

structnode*p;

for(p=head;p!=NULL;p=p->next)

{

printf("%d",p->data);

}

printf("\n");

}

intmain(void)

{

structnode*head=NULL;

structnode*p;

inti;

/**

*初始化鏈表

*/

srand((unsigned)time(NULL));

for(i=1;i<11;++i)

{

p=(structnode*)malloc(sizeof(structnode));

p->data=rand()%100+1;

if(head==NULL)

{

head=p;

head->next=NULL;

}

else

{

p->next=head->next;

head->next=p;

}

}

print_list(head);

printf("\n");

QListSort(&head,NULL);

print_list(head);

system("pause");

return0;

}

voidQListSort(structnode**h