《《数据结构》实验报告——排序.pdf》由会员分享，可在线阅读，更多相关《《数据结构》实验报告——排序.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、其身正，不令而行；其身不正，虽令不从。论语人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武数据结构实验报告 排序 实验题目：输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。实验所使用的数据结构内容及编程思路：1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。一般情况下，第 i 趟直接插入排序的操作为：在含有 i-1 个记录的有序子序列 r 1.i-1 中插入一个记录 r i 后，变成含有 i 个记录的有序子序列 r 1.i；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标
2、出界，在 r0处设置哨兵。在自 i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行 n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第 2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为s，s+1,t,首先任意选取一个记录(通常可选第一个记录s)作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位
3、置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置 i 作为界线，将序列s，t分割成两个子序列i+1,L.i+2,t。这个过程称为一趟快速排序，或一次划分。一趟快速排序的具体做法是：附设两个指针 low 和 high，他们的初值分别为 low 和 high，设枢轴记录的关键字为 pivotkey，则首先从 high 所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从 low所指位置起向后搜索，找到第一个关键字大于 pivotkey 的记录和枢轴记录互相交换，重复这两不直至 low=high 为止。具体实现上述算法是，每交
4、换一对记录需进行 3 次记录移动（赋值）的操作。而实际上，在排列过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即 low=high 的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存在 r0的位置上，排序过程中只作 rlow或 rhigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，人人好公，则天下太平；人人营私，则天下大乱。刘鹗丹青不知老将至，贫贱于我如浮云。杜甫否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。3.简单选择排序：其操作为，通过 n-i 次关键字间的比较，从 n-i+
5、1 个记录中选出关键字最小的记录，并和第 i（1in）个记录交换之。显然，对1n中的记录进行简单选择排序的算法为：令 i 从 1 至 n-1，进行 n-1 趟选择操作。可以看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为 3（n-1）。然后，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为 n(n-1)/2。程序清单：1插入排序：#include struct sqlist int key11;int length;insertsort(struct sqlist*l)int i,j;for(i=2;ilength;i+)if(l-keyik
6、eyi-1)l-key0=l-keyi;l-keyi=l-keyi-1;for(j=i-2;l-key0keyj;j-)l-keyj+1=l-keyj;l-keyj+1=l-key0;main()int i,j,k;struct sqlist num;=10;for(i=1;i=;i+)scanf(%d,&i);insertsort(&num);printf（“charu：”）；以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。旧唐书魏征列传一寸光阴一寸金，寸金难买寸光阴。增广贤文for(i=1;i=;i+)printf(%d,i);测试用例：输入：23 34 12 98 56
7、 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 2 快速排序：#include struct sqlist int key11;int length;int partition(struct sqlist*l,int low,int high)int pivotkey;l-key0=l-keylow;pivotkey=l-keylow;while(lowhigh)while(lowkeyhigh=pivotkey)high-;l-keylow=l-keyhigh;while(lowkeylowkeyhigh=l-keylow;l-keylo
8、w=l-key0;return low;void qsort(struct sqlist*l,int low,int high)int pivotloc;if(lowlength);main()int i,j;struct sqlist num;=10;for(i=1;i=;i+)scanf(%d,&i);quicksort(&num);printf（“kuaisu：”）；for(i=1;i=;i+)printf(%d,i);测试用例：输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 3 选择排序：#incl
9、ude struct sqlist int key11;int length;int selectminkey(struct sqlist*l,int a)int i,j=a;for(i=a;ilength;i+)if(l-keyikeyj)j=i;return j;void selectsort(struct sqlist*l)int i,j,k;for(i=1;ilength;i+)勿以恶小而为之，勿以善小而不为。刘备古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼 j=selectminkey(l,i);if(i!=j)k=l-keyi;l-keyi=l-keyj;l-keyj=k
10、;main()int i,j;struct sqlist num;=10;for(i=1;i=;i+)scanf(%d,&i);selectsort(&num);printf（“xuanze：”）；for(i=1;i=;i+)printf(%d,i);测试用例：输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 编程感想：本次编程总共使用了三种排序方法，而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻的了解。首先，三种排序中，我们都像查表那样，设置了哨兵，而哨兵的使用可以减少对整个表的验
11、空操作，使程序更加节省空间。其次，对于插入排序，每次都要对一段序列进行检索，每排一次所要检索的序列长度减一，其时间发杂度为 O（n2）。接着，对于快速排序，这个程序是比较复杂的，总共是 3 个函数，并且使用了递归的方法，这是但是，这种算法却是最优越的，平均性能也是最好的，我在编这个程序时，对其排序的思想有了进一步的了解，并努力拿他与冒泡排序进行比较，看出了些许其优越性。还有，就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样，都是 O（n2），性能不如快速排序。最后，本次试验是数据结构课的最后一次实验，经过数据结构试验课的锻炼，人人好公，则天下太平；人人营私，则天下大乱。刘鹗吾日三省乎吾身。为人谋而不忠乎？与朋友交而不信乎？传不习乎？论语使我对数据结构有了更深刻的理解，对我对其知识起到了重要的影响，增加了我编程的实践活动，为我将来进一步学习打下了基础。