实验报告单排序

1 / 15 实验报告单排序 数据结构实验报告 实验名称：实验四 排序 学生姓名： 班级： 班内序号： 学号： 日期： 2016 年 12月 21日 1、 实验要求 题目 2 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据 分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数。 3、对于这三类数据，比较上述排序算法中不同算法2 / 15 的执行时间，精确到微秒。 4、对 2和 3 的结果进行分析，验证上述各种算法的时间复杂度。 编写测试 main函数测试线性表的正确性。 2、 程序分析 存储结构 说明：本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 单链表存储结构： 结点结 构 struct Node int data; Node * next; ; 示意图： 关键算法分析 一：关键算法 直接插入排序 void LinkSort:InsertSort 直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。 算法自然语言 3 / 15 1.将整个待排序的记录序列划分成有序区和 无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录； 2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录； 3.重复执行 2，直到无序区中没有记录为止。 源代码 void LinkSort:InsertSort /从第二个元素开始，寻找前面那个比它大的 Node * P = front-next; /要插入的节点的前驱 while Node * S = front; /用来比较的节点的前驱 while CompareCount+; if / P 的后继比 S的后继小则插入 要插入 4 / 15 insert;break; S = S-next; if P = P-next;break; /若一趟比较结束，且不需 时间和空间复杂度 最好情况下， 待排序序列为正序，时间复杂度为 O。 最坏情况下，待排序序列为逆序，时间复杂度为 O。 直接插入排序只需要一个记录的辅助空间，用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。 直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现，当序列中的记录基本有序或带排序记录较少时，他是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率减低。 插入到合适位置 直接插入排序过程 冒泡排 序 void LinkSort:BubbleSort 冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。本程序采用改进的冒泡程序。 算法自然语言 1.将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。 5 / 15 2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移，关键码大的记录向后移。 3.将最后一次交换的位 置 pos，做为下一趟无序区的末尾。 4.重复执行 2 和 3，直到无序区中没有反序的记录。 源代码 void LinkSort:BubbleSort Node * P = front-next; while /第一趟排序并查找无序范围 CompareCount+; if swap; P = P-next; Node * pos = P; P = front-next; while Node * bound = pos; 6 / 15 pos = front-next; while CompareCount+; if swap; pos = P-next; P = P-next; P = front-next; 时间和空间复杂度 在最好情况下，待排序记录序列为正序，算法只执行了一趟，进行了 n-1次关键码的比较，不需要移动记录，时间复杂度为 O； 在最坏情况下，待排序记录序列为反序，时间复杂度为 O，空间复杂度为 O。 冒泡排序是一种稳定的排序方法。 反序则交换 快速排序 void LinkSort:Qsort 算法自然语言 7 / 15 1.首先选一个轴值，将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值。 2.然后分别对这两 部分重复上述过程，直到整个序列有序。 3.整个快速排序的过程递归进行。 源代码 void LinkSort:Qsort Node * End = front; while End = End-next; Partion; void LinkSort:Partion if/递归返回 return ; Node * Mid = Start; /基准值前驱 Node * P = Mid-next; 8 / 15 while CompareCount+; if /元素值小于轴点值，则将 数据结构实验报告排序 实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序 的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第 i 趟直接插入排序的操作为：在含有 i-1 个记录的有序子序列 r 1.i-1中插入一个记录 r i后，变成含有 i 个记录的有序子序列 r 1.i；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在 r 0处设置哨兵。在自 i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行 n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第 2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一9 / 15 部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为 s， s+1,?t,首先任意选取一个记录作为枢轴，然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置 i作 为界线，将序列 s， ?，t分割成两个子序列 i+1,L.i+2,?,t。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针 low 和 high，他们的初值分别为 low 和high，设枢轴记录的关键字为 pivotkey，则首先从 high 所指位置起向前搜索找到第一个关键字小于 pivotkey 的记录和枢轴记录互相交换，然后从 low 所指位置起向后搜索，找到第一个关键字大于 pivotkey的记录和枢轴记录互相 交换，重复这两不直至 low=high 为止。 具体实现上述算法是，每交换一对记录需进行 3 次记录移动的操作。而实际上，在排列过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即 low=high 的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存在 r0的位置上，排序过程中只作 rlow或 rhigh的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。 整个快速排序的过程可递归进行。若待排序列中只10 / 15 有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。 3.简单选择排序：其操 作为，通过 n-i 次关键字间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第i 个记录交换之。 显然，对 1?n中的记录进行简单选择排序的算法为：令 i 从 1 至 n-1，进行 n-1 趟选择操作。可以看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“ 0”，最大值为 3。然后，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为 n/2。 程序清单： 1插入排序： #include structsqlist int key11; int length; insertsort inti,j; for if 11 / 15 l-key0=l-keyi; l-keyi=l-keyi-1; for l-keyj+1=l-keyj; l-keyj+1=l-key0; main inti,j,k; structsqlistnum; =10; forscanf); insertsort; printf； forprintf; 测试用例： 输入： 23 34 12 98 56 45 67 8 9 37 输出： charu： 8 9 12 23 34 37 45 56 67 98 2快速排序： #include structsqlist 12 / 15 int key11; int length; ; int partition intpivotkey; l-key0=l-keylow; pivotkey=l-keylow; while whilehigh-; l-keylow=l-keyhigh; whilelow+; l-keyhigh=l-keylow; l-keylow=l-key0; return low; voidqsort intpivotloc; if pivotloc=partition; qsort; qsort; void quicksort 13 / 15 qsort; main inti,j; structsqlistnum; =10; forscanf); quicksort; printf； forprintf; 测试用例： 输入： 23 34 12 98 56 45 67 8 9 37 输出： charu： 8 9 12 23 34 37 45 56 67 98 3选择排序： #include structsqlist int key11; int length; intselectminkey inti,j=a; 14 / 15 for;ilength;i+) ifj=i; return j; voidselectsort inti,j,k; for j=selectminkey; ifk=l-keyi; l-keyi=l-key