logo资料库

内排序性能比较（c数据结构课程设计）.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.20M 资料格式：doc 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    数据结构课程设计报告 题目： 各种内部排序性能比较 学生姓名： 学 号： 班 级： 指导教师： 2010 年 6 月 3 日
    一、需求分析说明： 排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优 缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：插入法 排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移 动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的 方法消耗最短的时间完成排序。 二、总体设计： 本程序主要包括八个功能： 1、直接插入排序 2、二分法插入排序 3、shell 插入排序 4、直接选择排序 5、冒泡排序 6、快速排序 7、归并排序 8、7 种排序比较 因此在类 Sort 定义中主要包括这八个函数。以及需要用到的变量。 主函数中包括产生待排序序列、提示用户选择排序方法或比较各种排序的时 间复杂度。并使用 while 循环使用户可以连续选择想要程序做的操作，直到选择退出 程序为止。 main → 直接插入排序 insertsort → → → → → 二分法插入排序 binarysort shell 插入排序 shellinsertsort 直接选择排序 simplesectsort 快速排序 quicksort 归并排序 mergesort mergesort → 7 种排序比较 checkdouble merg e 2
    Main(): 输出各菜单→提示用户选择菜单→产生随机数序列→ 进入 while 循环 →若选择 1，则调用 insertsort（）函数进行直接插入法排序 ，并输出各趟排序结果 和排序中元素比较移动次数 →若选择 2，则调用 binarysort（）函数进行二分法插入排序，并输出各趟排序结果 和排序中元素比较移动次数 →若选择 3，则调用 shellinsertsort（） 函数进行 shell 插入排序，并输出各趟排序 结果和排序中元素比较移动次数 →若选择 4，则调用 simplesectsort（）函数进行直接选择排序，并输出各趟排序结 果和排序中元素比较移动次数 →若选择 5，则调用 bubblesort（）函数进行冒泡法排序，并输出各趟排序结果和排 序中元素比较移动次数 →若选择 6，则调用 quicksort（）函数进行快速法排序，并输出各趟排序结果和排序 中元素比较移动次数 →若选择 7，则调用 mergesort（）函数进行归并排序，并输出各趟排序结果和排序 中元素比较移动次数 →若选择 8，则调用 checkdouble（）函数进行 7 次排序，并输出比较结果和排序中 元素比较移动次数 →若选择 0，则退出程序 三、详细设计： 1、直接插入法排序： 将序列中第一个元素作为一个有序序列，将剩下的 n-1 个元素插入该有序序列中，插 入后保持该序列有序。在将一个元素插入到有序表中时，首先将其存入临时变量 temp 中，然后从后往前查找插入位置，当 temp 小于表中元素时，就将该元素后移，继续 比较移动，直到 temp 大于等于表中元素或者到了有序表中第一个元素时结束，这时 就可将 temp 存入刚后移的元素的位置了。次种排序法必须执行 n-1 趟，最好情况下， 每趟排序只比较一次，移动两次。最坏情况下，最多比较 i 次，移动 i+2 次。 2、二分法插入排序： 根据插入排序的基本思想，在找第 i 个记录的插入位置是，前 i-1 个记录已排序，将 3
    第 i 个记录的排序码 key[i]和已排序的前 i-1 个的中间位置记录的排序码进行比较，如 果 key[i]小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后 半部继续使用二分法，知道查找范围为空，即可以确定 key[i]的插入位置。 3、Shell 插入排序： Shell 插入排序又称缩小增量排序算法。 Shell 插入排序的具体做法是：对有 n 个记录进行排序，首先取 1 个整数 d
    此排序算法是一个递归算法。定义函数 Qsort(),实现具体排序过程。每趟排序的结果 是将当前序列分割为两个子序列：左边的元素全部小于分割元素，右边的子序列全部 大于分割元素。再对两个子序列进行快速排序，依次循环，直到子序列为空或只有一 个元素时结束。定义变量 left 和 right 分别指向原始序列的第一个和最后一个元素，i 和 j 为游动指针，初始化 i=left；j=right+1; 设待排序序列的第一个元素为分割元素。i 从左向右扫描，找到第一个大于或等于分 割元素的元素时结束，j 从右往左扫描，找到第一个小于或等于分割元素的元素时结 束，若 i=j 时结束。再交换 A[left]和 A[j]，完成 一趟排序。再调用本函数对低端序列和高端序列快速排序。在函数 quicksort()中，定 义变量 int h 来保存原始序列的元素个数，以便后面输出每趟排序结果时使用。再调 用函数 Qsort（）。 7、归并法排序：将有 n 个元素的序列看成是 n 个长度为 1 的有序子序列，然后两两 合并子序列，得到不少于 n/2 个长度为 2 或 1 的有序子序列；再两两合并，…，直 到得到一个长度为 n 的有序序列时结束。Merge（）函数只将 A 中相邻的两个子序列 合并为一个子序列。i1、j1，i2、j2 分别是子序列 1、2 的上下界，T *temp=new T[j2-i1+1] 分配能存放两个子序列的临时数组，用于保存合并的中间结果，本趟合并结束后，再 将临时数组中的元素“倒回”到 A 中。Mergesort（）函数中，首先令子序列中的元 素个数 size=1，然后求出相邻两个子序列的下标 i1,j1,i2,j2，调用子函数 merge （A,i1,j1,i2,j2）将它们合并，合并完成后，size 扩大一倍，即 size*=2;继续这一过程， 直到 size>=n 时结束。程序中第二个 while 循环用于控制同 size 大小的子序列两两合 并，若 i1+size>=n，则说明 A 数组中只剩下一个子序列，无需再进行合并，此趟排 序结束。全部排序的比较，一次调用前七种排序方法，然后让用户根据数据比较其中 的好坏。 8、main()函数： Do while 循环，此 while 循环的条件是 1，直到选择了退出程序，即菜单 0，才调用 系统函数 exit（0）结束循环，退出程序。 四、代码： #include #include 5
    r[maxsize+1]; #define maxsize 100 typedef int keytype; typedef struct{ keytype key; int other; }recordtype; typedef struct{ recordtype int length; }table; typedef struct{ int count1[8]; int count2[8]; }count; count int m=0; int rand(void); void show(table *); void insertsort(table *tab) { t1.count1[1]=1; t1.count2[1]=0; printf("直接插入排序：\n"); for(i=2;i<=tab->length;i++) {j=i-1; tab->r[0]=tab->r[i]; t1.count2[1]+=2; while(tab>r[0].keyr[j].key t1={0}; int i,j; t1.count1[1]++; { 6
    tab->r[j+1]=tab->r[j]; j=j-1; t1.count2[1]++; } tab->r[j+1]=tab->r[0]; printf("第%d 趟:", i-1); show(tab); } printf("直接插入排序元素比较的次数为：%d,交换的次数 为:%d\n",t1.count1[1],t1.count2[1]); } void binarysort(table *tab) { int i,j,left,right,mid; t1.count1[2]=1; t1.count2[2]=0; printf("二分插入排序：\n"); for(i=2;i<=tab->length;i++) { tab->r[0]=tab->r[i]; left=1;right=i-1; while(left<=right) { mid=(left+right)/2; if(tab->r[i].keyr[mid].key ) { right=mid-1;t1.count1[2]++;} else left=mid+1; } for(j=i-1;j>=left;j--) {tab->r[j+1]=tab->r[j];t1.count2[2]++;} 7
    tab->r[left]=tab->r[0];t1.count2[2]+=2; printf("第%d 趟:", i-1); show(tab); } printf("二分插入排序元素比较的次数为：%d,交换的次数 为:%d\n",t1.count1[2],t1.count2[2]); } void shellinsertsort(table *tab) { int i,j,d,m=0; t1.count1[3]=1; t1.count2[3]=0; printf("shell 插入排序：\n"); d=tab->length/2; while(d>=1) { for(i=d+1;i<=tab->length;i++) { tab->r[0]=tab->r[i]; j=i-d; while(tab->r[0].keyr[j].key && j>0) t1.count1[3]++; { tab->r[j+d]=tab->r[j]; j=j-d; t1.count2[3]++; } tab->r[j+d]=tab->r[0]; t1.count2[3]+=2; } d=d/2; 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料