《2023年数据结构实验报告实现典型的排序算法.docx》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告实现典型的排序算法.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、佛山科学技术学院实 验 报告课程名称数据结构实验项目实现典型的排序算法专业班级1 0网络工程2姓 名 张珂卿 学号 指导教师 成绩 日期 2023. 11. 2 7一、实验目的1 .掌握排序的基本概念；2 .熟悉排序中使用的存储结构,掌握多种排序算法，如堆排序、希尔排序、快速排序算法 等。二、实验内容1 .几种典型的排序算法；2 .计算不同的排序算法的时间复杂度；3 .鉴定某种排序算法是否稳定的标准。三、实验原理排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有 序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完毕，则称 此类排序问题为内部排序。
2、反之，若参与排序的记录数量很大，整个序列的排序过程不也许 在内存中完毕,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序 序列长度的过程。四、实验环节1 .输入记录的基本结点与信息，选用相关的存储结构，完毕记录的存储、输入的初始化工 作。2 .选择“直接插入排序”，“希尔排序”，“快速排序”，“简朴选择排序”和“堆排序”几种 排序中的任意三种排序，编程实现排序算法。用菜单形式选择排序方法，并显示排序过程和 排序结果。3 .计算排序算法的时间复杂度并进行稳定性分析。Se 1 ect Sort (Elem_Arr);C OU t 简朴矗择排序结果为：e n dl;6how E 1
3、 em Arr (E lem A r r);else i f ( a = = 5) gint NO;c out*请输入需要排序元素个数：” NO ;1 e n=N0+l;o E 1 em_Arr= n ew i n t 1 en;r eat E 1 e m Arr (E 1 em Arr);HeapSor t (Elem Arr);ocout堆排序结果为:e ndl;Sho wElem_Arr(Elem_Arr);else i f(a= = 6)o (bin t NO;acoutN0;le n=NO+l;oElem_Arr = ne w i n t len；6 C r eatE 1 em Ar
4、r ( E 1 em Arr);M e rgeSort (Ele m_A r r )；-cout “归并排序结果为：e ndl;o ShowElem A r r (Elem Arr);) 一o e Ise if (a=7)( SLList L; o Rad i xSor t (L)； 3e 1 se cout输入错误! H e n d 1;co u t n e nd 1 ;ocou t 操作完毕，请输入“1”返回主菜单，否则请按其他任意键退出！endl；C O UtZ/，zc;oif (c=l)o o p erat e (Elem Arr)；void main()i n t *Elem_ Ar
5、r； opera t e (E lem_Arr);程序结果截图:请输入需要排序元素个数:请依次输入元素：21 13 55直接排序结果为：集作完毕，请输入“1 ”返回主菜单，否则请按其他任意键退出!12 3 数数数 .JA.JA.1A 请请请 -二一二二F 士于毛丁 士下营输入需要排序元素个数：常依次输入元素：41 21 57 48 33快速排序结果为：21 33 41 48 57 操作完毕，请输入“工”返回主菜单，否则请按其他任意键退出！六、实验结果分析及实验体会通过这次数据结构我感觉自己收获还是挺多的,这次实验课做的课题是实现典型的排序 算法,我最大的收获是感受到了计算机的真正运营原理，用这
6、些代码来代替人为地工作,很久 以前我觉得这是不可思议的事情，但是我今天居然也做到了。这次数据结构实验课，激发了 我对学习的积极性，从程序编写，整理资料到完整运营，最后做调试的过程中，感觉到自己所 学习的专业课也并不是那么枯燥乏味，并且明白了之前学不太好的因素，这门课的确需要以 后不断的思考和实践，才可以逐渐提高自己专业课汲取知识的能力。五、程序源代码及注释#inc 1 u de i ost r e am us i ng n a mespac e std； #defi n e MAX_N0_0 F _KEY 8#de f i n e RADIX 10 关键字基数 # define MAX_SPA
7、CE 1 0 00typedef stru c t o i nt keys MAX_N0_0F_KE Y1 n t d a ta;其他数据项 o i nt next;) SL Ce1 1 ;typed e f s true t(oSLCe 1 1 rMAX_SPACE ; /静态链表可运用空间i n t key num; / /记录的当前关键字个数i n tr ecnum;静态链表的当前长度 SLLis t ;typ e d e f i n t A r r T y p e R ADIX; 指针数组类型i n t 1 e n ; / /数组长度插入排序void Dire c tl n sertS
8、o r t (int E lem_Ar r ) i n t i , j;6for (i=2; i = 1； j)8 i f (Elem Arr 0 E 1 e m_Arr j)6Elem Ar r j+ 1 =E 1 em_Arrj;吃1 se break;dEleni_A r r j+ 1 = E 1 em_A r r 0;) /希尔排序voi d Shelllnsert( int Elem_Arr , int add) / / a dd 为某趟希尔排序的 增量一(int i ,j;of or (i=ad d + 1 ; iO&El e m_Arr j E1 e m_Ar r 0 ; j-=
9、 add) a E 1 em_Arr j+a d d=El e m_Arr j;El e m_Ar r j +a d d = E lem_A r r 0；1 void S he 1 ISort ( in t Elem Arr ) o i nt t ;ocout请输入增量数组元素个数:t;i n t *dl t a=new i n t t；0cout请依次输入增量数组元素：Ve n d 1;ofor(int i =0； i d lta i ;ofo r (int k = O;kt;+k)She 1 1 I n sert (El e m_Arr, dlta k ) ； /一趟增量为 d ltak的
10、插入排序 一快速排序int Parti t ion(int Elem A r r , int i, i n t j) /实现一分为二，pivotkey 为枢 轴变量oin t pivot key；opiv o t key=El e m A r r i ;while (i j)。awhile (i=pi v otke y )0。一j ；E 1 e m A r r i = E 1 em Arr j ；wh ile(ij&El e m A r ri=pivotk e y )o+i ；Elem_Arr j =E 1 em_Arr i ;oElem A r r i =pivotkey;oretur n
11、i ;/Pa r t i t i o nvo i d Q S o rt (int Elem Ar r , i nt low, in t high) -2 nt p iv o t 1 o c ;oif (low high)gpivo t 1 oc=Partiti o n (El e m_Ar r , low, h i gh) oQ S ort (E 1 em_A r r , 1 o w, pi v otl o c -1); oQ S o rt (Elem Arr, p ivotl o c+ 1 , h i gh)；void QuickS o r t (int Elem Arr )( -oQ S
12、o r t (Elem_Arr, 1, 1 e nl); /简朴选择排序in t Se 1 e ctM i n(int Elem Arr 口，int i ) ( oint min=i;o f o r (int j= i +1; j ElemArrj)8m in = j;Met u r n min; void S e 1 e ct S or t (int Elem_Ar r )(int t, j ;f o r ( i nt i =1; ilen;+i)j=Sele c tMi n (El e m_Arr, i );si f ( i ! = j) 8t=El e m_A r ri;9E 1 em
13、Arr i =E1 e m_Arrj;o E lem Ar r j = t ;) /Se 1 ectSort/堆排序void Hea p A d just (int Elem_A r r , int i , int m) oE 1 e m_Arr0 =Elem_Arr i;for ( int 2 *i ; j=m ; j * = 2 )g i f (jm&E 1 em_Arr j Elem_Arrj)“break；Eleni_Arr i=Elem_Ar r j;o i=j； )E1 e m_A r r i = E lem_Arr 0; 一vo i d HeapSort (int E 1 em
14、Arr )( fo r (int i = (le n-1) /2; i 0;-i)Wie a pAdjust (Elem_Ar r , i , len-1);for ( i =len- 1 ; il； - i ) (比 1 em_Arr 0=Elem A r r i;Elem_Arr i =E1 e m_Ar r 1;1 em_Arrl=Elem_Arr0;Heap Adjust ( E lem_Arr, 1 , i 1)； )归并排序void Mer g e ( i n t E 1 emArrl 口 , in t Elem_Arr , i n t i , int m, in t n) / 将
15、有序的SR i和SRm+L . n归并为有序的TRoint j, k ;ofor (j=m + l, k = i ; i=m& j=n;+ k )。将SR中记录由小到大地并入TRif (Elem_Arrl i E lem_A r r 1 j)Ele m Ar r k=El e mArrl i+；gel s eg Ele m_Arr k = E lem Arrl j +;if (i=m)/T R k. . n=S R i. m;将剩余的 SRi. m复制到 TRwhile ( k = n&i=m)g E 1 e m_Ar r k+ + = E lem_A r rl i+ + ；g i f(j=n
16、)将剩余的S Rj. n复制到TRb w h i le(k=n& j =n)oElem_Arrk+ =E 1 e m_Arr 1 j + + ; void MSo r t (int Elem_ Arrl , in tElem_Arr , int s, int t) /将 SRs.t归并排序为TRls.tint m；int TR 2 20;if (s=t)Elem_Ar r t = E lem Arrl s;oel s e(om =(s+t)/2 ;/将 SRs.t平分为 SRs.in和 SRm+L . t oM S o r t (E 1 em_Arrl, TR2, s, m);递归地将SR S
17、.m归并为有序的TR 2s. . mo MSort (Elem_Arrl, TR2, m+ 1 , t); 将 SRm+ 1 . t归并为有序的 TR2 m+ 1. t 前e r g e (TR2, Elem_A r r , s,m, t ) ; /将TR2s. m和 T R2 m+L . t 归并到 TRls.t void Merg e Sort ( int E 1 e m_Arr ) 对顺序表 L 作归并排序。 -int *E 1 em_Ar r l=new i nt 1 e n ；o f o r (int i=0; ile n ； i+)Elem_Arrl i = E 1 em Arr
18、i;MSort (E 1 em Arrl, Elem A r r , 1, len1);) 一/基数排序int s u c c ( i nt f , int j ) (in t k = j ;f o r(j; j 1 0 ； j+ + )i f ( f j!=0) b rea k； else k + + ;oif (j10) re t urn k; e Ise r et u rn 0 ；v o id CreateL( S LList &L )(c o ut 请依次输入元素:Ve n d 1;of or (in ti= 1 ; iL.r i . d ata;，L. ri. k eys0=L. r
19、 i . d a t a%10；b L. r i . key s 1 = (L. r i . dat a %10 0 -L. r i . key s 0) /10;L. ri. k eys2 =L. ri . dat a / 1 0 0;ovoid D i stribute(SLL i st &L , int i, A r rType &f, Arr Typ e & e )(/ 算法 10.15o/静态链表L的r域中记录已按(keys0, .，keysi -1)有序，”/本算法按第i个关键字keysi建立RADIX个子表，使同一子表中记录的keys i 相同。f 0.RADIX-1和e 0.
20、. RADIX-1 。/分别指向各子表中第一个和最后一个记录。int j, p；for (j=0 ; jRAD I X;+ + j)o f j=0;ge j =0； /各子表初始化为空表of o r (p = L. r0. n ext ;p!=0； p=L. r p .next)。j =L.rp.keys i :/将记录中第i个关键字映射到0RADIX-1,-f (f j = =0)6 f j =P； o e 1 s eoL. r e j. next= p ;ej =p;/将p所指的结点插入第j个子表中/ / D istri b u t evoid P r int S LL i st ( S
21、L L ist L, int i)( ofor ( i n t p = L r 0. n ext; p ! = 0 ； p=L. rp. next)o cout L. rp. data/ ;void Collect (SL L ist &L, Ar r Type f, Arr Type e)”/本算法按keys i 自小至大地将f0. . RADIX - 1 所指各子表依次链接成/ 一个链表，e0. .RADIX- 1 为各子表的尾指针i n t t , j =0;j= s ucc ( f , j)；L. r0. nex t = f j ;/ L. r0. n e x t指向第一个非空子表中第
22、一个结点 t=e j;j + ；j=su c c(f, j );whil e (j !=0&f j !=0) /找下一个非空子表/链接两个非空子表L. rt. nex t = f j;t=e j; j+;j = s u cc(f, j)；i f (su c c(f, j )= = 0)o bre a k ；)L.rt.ne x t = 0；/ t指向最后一个非空子表中的最后一个结点void Ra d ix S ort (SLList &L) (。/ L是采用静态链表表达的顺序表。对L作基数排序，使得L成为按关键字自小到大的 有序静态链表，L.r0为头结点。int i;ArrType f, e;
23、1. keynum=3;cout请输入所需排序元素个数(当前记录关键字个数=3 ) ： L . recn u m；oC r e a teL(L);f or (i=l; i =L. recnum;+i)L.ri-l. next=i;L. r L. recn u m. n ex t =0;/将L改造为静态链表f o r (i=0; iL. keynum; +i) / /按最低位优先依次对各关键字进行分派和收集Dis t rib u te (L, i, f, e) ;/ / 第 i 趟分派。Co 1 lect(L, f, e)；/ 第 i 趟收集o) 0coutV基数排序结果为：endl;P r i
24、nt_SLLis t ( L , i)； 一v o id CreatElem A r r (int Elem A r r ) (ocou t 请依次输入元素：Xendl；for( i n t i=l； iElem Arr i； void S h o w E lem Arr (in t Elem Arr ) for (int i= 1 ; il e n ； i +)oocoutElem_ Arr i ，z; void opera t e (in t Ele m_Arr ) oi n t a , b, c;C oV直接排序请输入数字1 Ven d 1;oco u t n希尔排序请输入数字2 n e
25、nd 1 ;。c ou t 快速排序请输入数字3z，en d 1;oc o ut n/za； oif (a=l)gin t NO；ooco u t ”请输入需要排序元素个数：N0;4en=N0+ 1 ;匕 E 1 em_Arr=new i n t 1 e n；C r e atE 1 e m_Ar r (Elem_Arr );i r e ctlnsert S ort (E 1 em_Arr);ocout V直接排序结果为:，endl;6sh o wElem Arr (E 1 e m A r r);。 一oels e if (a= = 2)(oint NO;ocou t 请输入需要排序元素个数：N
26、0 ;oolen=NO+l;o E lem_Ar r =new int le n ;Crea t El e m_Arr(Elem Arr)；h el 1 S o rt (E 1 em Arr);8co u tV ”希尔排序结果为：e n d 1 ；Sho wE 1 em_A r r (Elem Ar r )；else i f (a=3)(n t NO;b co u t N O ;len=NO+l;oE lem Ar r =new i nt len;CreatEl e m_Ar r (Elem Arr);Quic k Sort(Elem Arr);cout快速排序结果为： end 1 ;o ShowE lem Ar r (E 1 em Arr);。2 1 se if (a = =4)。gint NO;ocout ”请输入需要排序元素个数：n NO;4 e n=N0+l;Elem_Arr=new int len;ooCreat E 1 em A rr (E1 em Arr);