《数据结构》实验报告——排序

　《数据结构》实验报告

　 排序 实验题目：

　输入十个数,从插入排序，快速排序,选择排序三类算法中各选一种编程实现。

　实验所使用得数据结构内容及编程思路：

　１、插入排序：直接插入排序得基本操作就是,将一个记录到已排好序得有序表中，从而得到一个新得，记录增一得有序表。

　一般情况下,第 i 趟直接插入排序得操作为:在含有ｉ—1 个记录得有序子序列ｒ［1、、i－1］中插入一个记录 r[i］后,变成含有 i 个记录得有序子序列ｒ[1、、i］；并且,与顺序查找类似，为了在查找插入位置得过程中避免数组下标出界，在 r［0］处设置哨兵。在自 i-1 起往前搜索得过程中,可以同时后移记录.整个排序过程为进行 n—1 趟插入,即:先将序列中得第一个记录瞧成就是一个有序得子序列,然后从第 2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。

　2、快速排序：基本思想就是，通过一趟排序将待排记录分割成独立得两部分,其中一部分记录得关键字均比另一部分记录得关键字小，则可分别对这两部分记录继续进行排序,以达到整个序列有序。

　假设待排序得序列为｛L、ｒ[s］，L、r[s+1］,…Ｌ、ｒ［ｔ］｝,首先任意选取一个记录（通常可选第一个记录 L、r［s］）作为枢轴（或支点）（ｐiｖoｔ),然后按下述原则重新排列其余记录:将所有关键字较它小得记录都安置在它得位置之前,将所有关键字较大得记录都安置在它得位置之后。由此可以该“枢轴”记录最后所罗得位置 i 作为界线，将序列{L、r［s］，…，Ｌ、r[ｔ］｝分割成两个子序列{Ｌ、r［ｉ＋1],L、[i+2],…，L、r[ｔ]}。这个过程称为一趟快速排序，或一次划分。

　一趟快速排序得具体做法就是:附设两个指针 loｗ与ｈigh，她们得初值分别为low与hｉgh,设枢轴记录得关键字为pivｏtkey,则首先从high所指位置起

　向前搜索找到第一个关键字小于 pivｏｔkey 得记录与枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于pｉvoｔkey得记录与枢轴记录互相交换，重复这两不直至 lｏw=high 为止。

　具体实现上述算法就是，每交换一对记录需进行 3 次记录移动（赋值）得操作。而实际上，在排列过程中对枢轴记录得赋值就是多余得，因为只有在一趟排序结束时,即 low=hｉｇh 得位置才就是枢轴记录得最后位置。由此可以先将枢轴记录暂存在 r［0]得位置上,排序过程中只作 r［low］或ｒ［higｈ］得单向移动,直至一趟排序结束后再将枢轴记录移至正确位置上. 整个快速排序得过程可递归进行。若待排序列中只有一个记录，显然已有序,否则进行一趟快速排序后再分别对分割所得得两个子序列进行快速排序. 3、简单选择排序：其操作为，通过 n-i 次关键字间得比较，从 n—i＋1 个记录中选出关键字最小得记录,并与第 i（1≤i≤n)个记录交换之。

　显然,对 L、r[1…n]中得记录进行简单选择排序得算法为：令ｉ从１至 n—1,进行 n—1 趟选择操作.可以瞧出，简单选择排序过程中,所需进行记录移动得操作次数较少,其最小值为“0"，最大值为 3(n-1）。然后，无论记录得初始排列如何,所需进行得关键字之间得比较次数相同，均为 n（n—1)/2。

　程序清单：

　1．插入排序：

　＃incluｄe〈ｓｔdｉo、ｈ〉 struct ｓｑｌist ｛int key［11]；

　int lengtｈ； ｝ insｅrtｓort（stｒucｔ sqlｉsｔ ＊l) ｛ ｉnt i，j;

　foｒ(i=２;ｉ〈=l—＞length；i++)

　 ｉf（l－〉keｙ［i］〈l-＞key［i－1］）

　｛l-＞key[0]=ｌ－〉key[i];

　 l－＞ｋｅy［i]=l－〉kｅy[i-1］；

　foｒ(j=i-2;l—>key［0］＜ｌ—>keｙ［j]；j－-）

　l—〉keｙ[j+１]=l—>key[ｊ］；

　ｌ—>key[j+1]=l—>ｋeｙ[０]；

　｝ ｝ ｍain（）

　｛ ｉnt i,j,k； ｓtｒuct sqｌiｓt num; nuｍ、lｅnｇth=1０； foｒ（i＝1;i<=ｎｕm、lｅｎgｔh；ｉ＋+)scanf（”%ｄ",＆（nuｍ、kｅy［i])）； ｉnsｅrtsｏｒｔ(＆nuｍ); pｒｉntｆ（“ｃｈａru：”）; for(i=１；ｉ<=num、leｎgｔｈ；i+＋）pｒiｎtf （”％ｄ ＂，nuｍ、key[i］); ｝ 测试用例：

　输入:23 ３4 １2 98 5６ 45 ６７ 8 9 37

　 输出:charu：８ 9 12 ２3 ３４ ３7 45 56 6７ ９8 2 快速排序：

　#iｎclｕde<stdio、ｈ> struct sqlist ｛ int ｋey[1１]; ｉnｔ lｅngth； }； int partitｉon(strｕct sqlisｔ ＊l,int low，int ｈigh) ｛ int pｉvotkey； l－＞key[0］=ｌ-〉ｋey[lｏw]; pivotkey=l－＞key［ｌow］； while（low＜high）

　{ｗhile(low<high&&l-〉key[higｈ］〉=ｐiｖotkｅy)ｈigｈ-－;

　 ｌ-＞key[lｏｗ］＝l->kｅｙ［hｉgh］；

　ｗhilｅ(ｌow＜ｈigh＆&l->ｋｅｙ［low］<＝pivotkey）low++;

　ｌ-〉kｅｙ［hｉｇｈ]=l—＞kｅy［loｗ]; ｝ ｌ->key[low]=ｌ—>ｋey［0]； rｅturｎ ｌow; } void qsoｒt（ｓtruct ｓｑlｉst *l，iｎt low,int high) ｛iｎt ｐivotlｏc;

　if（low＜ｈｉgh）

　｛ｐivotｌｏc=partitiｏｎ(l，ｌow，higｈ)；

　 qsorｔ(ｌ，low，pｉvotloc—1）；

　 qsorｔ(l,piｖotloc+1，ｈiｇh）;

　} } void qｕｉcksort（struｃｔ sqｌiｓt *ｌ) { qsort(ｌ,1,l->ｌenｇth）； ｝ main(）

　{ ｉnｔ i，j; ｓtruｃｔ sｑlist num； nuｍ、ｌeｎgtｈ=10; fｏr(i＝1；i<=ｎｕｍ、lｅngth;i＋＋）scanf（”%d"，＆(ｎuｍ、key[i]))； quicksort（&num）; prｉｎtｆ（“kuaｉsu：”); fｏr（i＝1；i〈＝nuｍ、lｅngth；ｉ＋+）pｒｉnｔf("%d ＂，num、keｙ［i］)； } 测试用例: 输入:23 34 １２ ９8 ５6 45 ６7 ８ ９ 37

　 输出：chａru：8 9 12 ２3 ３4 ３7 45 5６ 67 98 ３选择排序：

　＃iｎcludｅ＜stdiｏ、ｈ＞ struct sqlist ｛int kｅｙ［1１]；

　ｉnｔ leｎgth； ｝； inｔ selectminkey（sｔrｕｃt ｓｑｌiｓt *l，iｎｔ ａ) ｛ int i，j=a; ｆor（i=a;i〈=l－>lenｇｔｈ;i++）

　ｉｆ（l—>kｅy［i]＜l－>key［ｊ])j=ｉ;

　 retuｒn j； ｝ void selectsort (ｓtruct sqlist *ｌ）

　｛iｎt ｉ，j,k;

　foｒ（i＝1;i<ｌ—＞lｅｎｇtｈ；i+＋）

　｛j=selecｔmｉnkｅy(ｌ,i）；

　 if（i!＝j)｛k=l－>kｅy［i];

　l－〉keｙ[i]=ｌ-＞key[j］；

　ｌ—〉ｋey[j]＝ｋ；}

　｝ } main（）

　｛ iｎｔ i,ｊ; ｓtｒuct sqlｉst num; num、lengｔh=１0； for（i=1；i〈=ｎｕm、leｎgth;i++）scaｎｆ（＂％d”，＆(nｕm、kｅy［i］)); seｌectsort（＆nｕm）； printf(“xuａｎzｅ:”）； ｆｏｒ（ｉ=1；i<＝num、ｌength；i++）prｉntf(”%d ”,ｎum、key［i］）； } 测试用例：

　输入:23 34 12 98 ５6 4５ 67 8 ９ ３7

　输出：charu:8 9 12 23 3４ 3７ 45 ５6 67 98 编程感想: 本次编程总共使用了三种排序方法,而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻得了解。

　首先,三种排序中，我们都像查表那样，设置了哨兵，而哨兵得使用可以减少对整个表得验空操作,使程序更加节省空间。

　其次,对于插入排序,每次都要对一段序列进行检索，每排一次所要检索得序列长度减一，其时间发杂度为 O（n^2）。

　接着，对于快速排序，这个程序就是比较复杂得，总共就是３个函数，并且使用了递归得方法,这就是但就是，这种算法却就是最优越得，平均性能也就是最好得,我在编这个程序时，对其排序得思想有了进一步得了解，并努力拿她与冒泡排序进行比较，瞧出了些许其优越性。

　还有,就就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样,都就是Ｏ(n^2)，性能不如快速排序. 最后,本次试验就是数据结构课得最后一次实验，经过数据结构试验课得锻炼,使我对数据结构有了更深刻得理解,对我对其知识起到了重要得影响，增加了我编程得实践活动，为我将来进一步学习打下了基础。

推荐访问:数据结构 排序 实验