1、實(shí)驗(yàn)5(高速、堆、基數(shù))排序算法設(shè)計(jì)一、實(shí)驗(yàn)?zāi)康暮鸵髮?shí)驗(yàn)?zāi)康模?.深入了解排序的定義和各種排序方法的特性，并靈活使用。2.熟悉常用的排序方法，并了解如何使用高級(jí)語言實(shí)現(xiàn)排序算法。3.了解各種方法的排序過程及其標(biāo)準(zhǔn)原理，并掌握分析各種排序方法性能的方法。實(shí)驗(yàn)要求：必須徹底了解有序的物理存儲(chǔ)結(jié)構(gòu)，并為此以后的實(shí)際利用奠定基礎(chǔ)。二、實(shí)驗(yàn)內(nèi)容和原理：(1)實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)快速排序、堆排序和基本排序算法。(2)實(shí)驗(yàn)原理：快速排序：基于要排序的n個(gè)數(shù)據(jù)之一，然后對(duì)所有數(shù)據(jù)進(jìn)行一次排序，再按基準(zhǔn)數(shù)據(jù)將所有數(shù)據(jù)分為兩部分；如果所有數(shù)值都小于基準(zhǔn)數(shù)字，則在此之前；如果所有數(shù)值都大于基準(zhǔn)數(shù)字，則對(duì)接下來的兩部分重

2、復(fù)此過程。排序堆：按相應(yīng)值大小的定義順序排列n個(gè)已排序的數(shù)據(jù)，以輸出堆頂部的最小數(shù)據(jù)(按最小值的堆排序)，然后將其馀數(shù)據(jù)重新設(shè)為堆，從而減小大小，重復(fù)生成輸出和堆，直到全部排序?；鶖?shù)排序：LSD方法：按最低關(guān)鍵字位k1對(duì)正在排序的數(shù)據(jù)的n個(gè)值進(jìn)行排序，按k1值排序的文件的n個(gè)記錄分配給多個(gè)堆，然后按k1值從最小到最大的順序收集k1值，接下來再按最高關(guān)鍵字子位k2的值分配和收集kn，然后繼續(xù)按最高關(guān)鍵字位分配和收集整個(gè)數(shù)據(jù)，直到按多個(gè)關(guān)鍵字位排序?yàn)橹?。三、?shí)驗(yàn)環(huán)境硬件：(1)學(xué)生用電腦；(2)多媒體實(shí)驗(yàn)教室；(3)局域網(wǎng)環(huán)境；軟件：(1)Windows XP中文操作系統(tǒng)；(2)turbo c 3

3、.0；四、算法說明和實(shí)驗(yàn)階段說明：(1)快速排序：范例：初始關(guān)鍵字36 73 65 97 13ijj左側(cè)掃描后36 73 65 97 13ij將Rj移至Ri 13 73 65 97 36ijI右掃描13 73 65 97 36ij移至Ri Rj，然后13 36 65 97 73ijI左側(cè)掃描13 36 65 97 73ijI左側(cè)掃描13 36 65 97 73ijI左側(cè)掃描13 36 65 97 73ijI=j第一次結(jié)束第一次對(duì)齊結(jié)束后13 36 65 97 73第二次對(duì)齊結(jié)束后13 36 65 97 733次對(duì)齊結(jié)束后，13 36 65 73 97(對(duì)齊結(jié)束)堆排序：43 33 61 82

4、72(初始狀態(tài))排序堆：范例：初始值6 12 11 10 81.將數(shù)據(jù)構(gòu)建為堆，n=5，從第三個(gè)數(shù)據(jù)開始，3，2，1數(shù)據(jù)篩選過程如下圖所示。6121110861211108121011682.創(chuàng)建初始堆后，需要從最后一個(gè)元素開始交換第k個(gè)元素和根，然后過濾根一次3.然后從-k元素開始交換，直到所有k=0對(duì)齊堆棧。排序條件：分為兩部分，第一個(gè)分配位置，第二個(gè)收集。創(chuàng)建在分配時(shí)用于存儲(chǔ)相同密鑰位的結(jié)構(gòu)數(shù)組。位數(shù)字是低關(guān)鍵字位，10位數(shù)字是高關(guān)鍵字位。關(guān)鍵字位值的范圍為0-9，qu I。f和qui。r是第一個(gè)隊(duì)列的頭和尾指針。Qui。f不是空的關(guān)聯(lián)鏈接列表被分為1位和10個(gè)字符來收集。收集完成后退出

5、，直到指定了所有關(guān)鍵字位。流程圖：(1)快速排序：結(jié)構(gòu)陣列：struct int low，high sN0/2 1；Int top=0，I，j，k；S top。low=1；Stop。high=n；當(dāng)Top不為零時(shí)重復(fù)I=stop。低；J=s top-。highK=partition(i，j)；S top。low=k 1；Stop。high=j；S top。low=I；Stop。high=k-1；K-1i是否K 1=R0。key i=1時(shí)為止SIF ter(j，n)j=n；j-；直到J=2R0=R1；R1=Rj；Rj=R0；Sift(1，j-1)；調(diào)用的函數(shù)sift(j，n):int k=2 *

6、 I；R0=RI；K=m時(shí)重復(fù)KRk。key是否CountRI=Rk；I=k；k=2 * I；計(jì)數(shù)；BreakkRk。keyR0。key是否RI=R0；(3)默認(rèn)對(duì)齊：Typedef struct node keytype keyStruct node * next NDStruct ND *f，* r； qu10；ND *p，* headInt i、j、k；長DD=1；值為1時(shí)重復(fù)I=0；I；到I10Qui。f=qui。r=空；I=1；I；I=到n；停止吧K=r I。key/DD；計(jì)數(shù)；p=(ND *)malloc(size of(ND)；Quk。f=NULL是否Quk。f=quk。r=p；

7、Quk。r-next=p；Quk。r=p；P-key=Ri。keyp-next=NULL；int flag=0；I=0；Head=qui。f；Qui。f=NULL時(shí)重復(fù)I；我九點(diǎn)重復(fù)j=I 1；J10 quj。f=NULL時(shí)重復(fù)j；計(jì)數(shù)；J=10是否BreakQui。r-next=quj。f；flag=1；I=j；Flag=0是否BreakI=0；I到i10停止吧Qui。f=qui。r=空；P=headDd *=10值為phead=p-next；k=p-key/DD；計(jì)數(shù)；Quk。f=NULL是否Quk。f=quk。r=p；Quk。r-next=p；Quk。r=p；Quk。r-next=NUL

8、L；P=headP=qu0。f；I=1；值為pQu0。f=p-next；Ri 。key=p-key；自由(p)；P=qu0。f；實(shí)驗(yàn)階段：程序代碼# include“stlib . h”# include“alloc . h”#define N0 30000Typedef int keytypeTypedef struct node /*創(chuàng)建可排序的編號(hào)*/Keytype key/*可排序的數(shù)字*/ Element元素RN0 1；/*保存要排序的數(shù)字集*/Int n=150/*將隨機(jī)繁殖數(shù)定義為150*/Void getData() /*隨機(jī)生成150個(gè)數(shù)字*/ int I；randomize()；for(I=1)；I=n；I)Ri。key=隨機(jī)(1000)；Void printData() /* getData()函數(shù)生成的數(shù)據(jù)輸出*/ int I；for(I=1)；I=n；I)printf(m ，Ri)。key)；/*數(shù)據(jù)輸出*/if(I % 8=0)printf( n )；printf(