数据结构 课程设计报告(排序算法比较)

数据结构课程设计报告学院：计算机科学与工程专业：计算机科学与技术班级：09级班学号：姓名：指导老师:时间: 2010年12月一、课程设计题目：1、哈夫曼编码的实现2、城市辖区地铁线路设计3、综合排序算法的比较二、小组成员：三、题目要求：1．哈夫曼编码的实现（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。

（2）针对上述统计结果，对各字符实现哈夫曼编码（3）对任意文章，用哈夫曼编码对其进行编码（4）对任意文章，对收到的电文进行解码2．某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线。

（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。

使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。

（3）输出应该建设的地铁路线及所需要建设的总里程信息。

3．综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。

试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。

（1）对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。

（2）待排序的表长不少于100，要求采用随机数。

（3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数（4）改变数据量的大小，观察统计数据的变化情况。

（5）对试验统计数据进行分析。

对各类排序算法进行综合评价。

四、项目安排：1、小组内分工合作分工：负责哈夫曼编码的实现，负责城市辖区地铁线路设计，负责综合排序算法的比较。

合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。

五、完成自己的任务：任务：综合排序算法比较1.思想实现流程图2.代码的实现#include<time.h>#include<stdio.h>#include<stdlib.h>#define MAXSIZE 1000int L[MAXSIZE+1];int num=100;intcount1=0,count2=0,count3=0,count4=0,count5=0,count6=0,count7=0,count8=0,count9=0,count10 =0;int creatdata() //产生随机数{FILE *f;int row;row=num/10;f = fopen("O_data.txt", "wt"); //创建并写入产生的随机数if(f){for(int i=0; i<10; i++) //控制列{for(int j=0; j<row; j++){fprintf(f, "%2d\t", rand()%100); //调用rand()函数控制为两位数}fprintf(f, "\n");}f close(f);}return 0;}void zjpx(int L[MAXSIZE]) //直接插入排序{creatdata();int i,j;for(i=2;i<=num;i++) // 从第二个开始插入{i f(L[i]<=L[i-1]){L[0]=L[i]; //设置哨兵并记录要插入的值L[i]=L[i-1];count2=count2+2; //如果if 成立则此处关键字移动for(j=i-2;(L[0]<L[j]);j--) //开始向前寻找{L[j+1]=L[j];count1++; //此处关键字比较count2++; //如果两次if成立则此处关键字移动} //记录后移L[j+1]=L[0]; //插入到正确位置count2++;}c ount1++;}printf("直接排序后的结果是:\n关键字比较了%d次\n关键字移动了%d次\n",count1,count2);for(i=2;i<=num;i++){p rintf("%2d ",L[i]);i f(i%10==0)printf("\n");}}void zbpx(int L[MAXSIZE]) //折半插入排序{creatdata();int i,j,m,low,high; //定义标志for(i=2;i<=num;++i) // 从第二个开始插入{L[0]=L[i];c ount4++; //此处关键字移动l ow=1,high=i-1;while(low<=high) //寻找插入位置{m=(low+high)/2; //折半找到位置if(L[0]<L[m]){high=m-1;} //判断是否需要移动位置并将折半区间进一步缩小else low=m+1;count3++; //在上次判断的时候已经做了关键字的比较所以比较次数自加}for(j=i-1;j>=high+1;j--){L[j+1]=L[j]; //记录后移count4++; //此处关键字移动}L[high+1]=L[0]; //插入记录count4++; //此处关键字移动}printf("折半插入排序后的结果是:\n关键字比较了%d次\n关键字移动了%d次\n ",count3,count4);for(i=2;i<=num;i++){p rintf("%2d ",L[i]);i f(i%10==0)printf("\n ");}}void xepx(int L[MAXSIZE],int num) //希尔排序{creatdata();int temp;int i,j,d;d=num/2; //确定第一次分组while(d>=1) //在第一组内进行向后的比较{f or(i=d+1;i<=num;i++) //对各组进行排序{temp=L[i];j=i-d;count6++; //如果while（d>=1）成立则此处有关键字的移动while((j>0)&&(temp<L[j])) //对组内进行排序{L[j+d]=L[j];j=j-d;count6++; //如果while 成立则此处有关键字的移动}count5++; //由于组内比较所以此处有关键字的比较L[j+d]=temp;count6++; //此处有关键字的移动}d=d/2;}printf("\n希尔排序后的结果是:\n关键字比较了%d次\n关键字移动了%d次\n ",count5,count6);for(i=2;i<=num;i++){p rintf("%2d ",L[i]);i f(i%10==0)printf("\n ");}}void mppx(int L[MAXSIZE]) //冒泡排序{creatdata();int flag=1;int temp;for(int i=1;i<=num && flag!=0;i++) //第一层循环排序{flag=0;for(int j=1;j<=(num-i);j++) //第二层循环排序{if(L[j]<L[j+1]){temp = L[j];L[j] = L[j+1];L[j+1] = temp; //进行排序flag=1;count8=count8+2; //如果if成立则此处有关键字的移动}count7++; //由于内部排序上面的if语句此处有关键字的比较}}printf("\n冒泡排序后的结果是:\n关键字比较了%d次\n关键字移动了%d次\n",count7,count8);for(i=1;i<num;i++){p rintf("%2d ",L[num-i]);i f(i%10==0)printf("\n ");}}void xzpx(int L[MAXSIZE]) //选择排序{creatdata();int i,j,k,temp;for(i=1;i<num;i++) //第一趟循环寻找最小记录{k=i;f or(j=i+1;j<=num;j++) //查找关键字最小的记录{if(L[k]<L[j]){k=j;} //查到最小记录的关键字然后与第一个数互换位置count9++; //此处有关键字的比较if(i!=k){temp=L[i];L[i]=L[k];L[k]=temp; //将关键字最小记录与还未排序的第一个数交换count10+=2; //如果if 成立则关键字有移动（!!!此处有问题显然if肯定有成立的时候所以count10会有值但是测试结果一直是0 搞不清原因）}}}printf("\n选择排序后的结果是:\n关键字比较了%d次\n关键字移动了%d次\n ",count9,count10);for(i=1;i<num;i++){p rintf("%2d ",L[num-i]);i f(i%10==0)printf("\n ");}}/*int partition(int L[MAXSIZE],int low,int high){int temp,t;int i,j,pos,flag;int change1,change2;temp=L[1]; //保存该元素的值pos=low; //记录当前位置change1=change2=0; //记录每次比较的起始元素，距离区间头或尾的偏移量do{f lag=1; //没有元素交换f or(i=high-change1;i>=pos+1;i--) //在左区间进行比较{if(L[i]<temp){t=L[pos];L[pos]=L[i];L[i]=t;pos=i; flag=0; change1++; //记录新的位置pos,偏移量增加break;}}i f(flag==0) //如果左区间有元素发生移动，则对右区间进行比较{flag=1;for(j=low+change2;j<=pos-1;j++) //从右区间的起始位置开始，一直到基准元素所处的位置{if(L[j]>temp){t=L[j];L[j]=L[pos];L[pos]=t;pos=j; flag=0; change2++;break; //如果有元素交换，flag置0，记录新的位置，偏移量增加}}}}while(flag==0);for(i=0;i<=7;i++)p rintf("%d ",*(a+i));printf("\n\n");return pos;}void kspx(int L[MAXSIZE],int b,int t){creatdata();int i;if(b<t){i=partition(L,b,t); //对区间(b,t)进行第一次划分k spx(L,b,i-1); //左区间进行划分k spx(L,i+1,t); //右区间进行划分}}*/void compare(int L[MAXSIZE]){printf("排序方式直接折半希尔冒泡选择\n");printf("比较次数%4d %4d %4d %4d %4d \n",count1,count3,count5,count7,count9);printf("移动次数%4d %4d %4d %4d %4d \n",count2,count4,count6,count8,count10); }void menu(int L[MAXSIZE]){int x;printf(" \n1 直接排序 4 冒泡排序7比较数据统计\n");printf(" ");printf(" \n2 折半排序 5 快速排序(未完成) 0 退出\n");printf(" ");printf(" \n3 希尔排序6选择排序\n");printf(" ");printf("\n请输入对应的序号查看结果\n");scanf("%d",&x);if(x>=0&&x<=7){s witch(x){c ase 0:exit(0);c ase 1:zjpx(L);menu(L);break;c ase 2:zbpx(L);menu(L);break;c ase 3:xepx(L,num);menu(L);break;c ase 4:mppx(L);menu(L);break;// case 5:kspx(L,0,10);menu(L);break;c ase 6:xzpx(L);menu(L);break;c ase 7:compare(L);menu(L);break;}}else{p rintf("输入有误！");m enu(L);}}void main(){creatdata();FILE* fp;int i=0;fp=fopen("O_data.txt","r"); //只读if(fp==NULL) //失败{p rintf("错误！");e xit(1); //中止程序}while(!feof(fp)) //从文件读出数据f scanf(fp,"%d",&(L[i++]));fclose(fp);printf("随机生成的数为:\n");for(i=0;i<num;i++){i f(i%10==0)p rintf("\n");p rintf("%2d ",L[i]);}printf("\n");menu(L);}3.实验数据分析：本实验共成功测试了5个排序方法，除了选择排序的关键字比较出现问题外实验结果全部合理正确，在统计关键字比较以及移动的问题上，与预想的结果相差不大，可以认为测试基本成功。

数据结构专业课程设计十种排序算法比较合肥学院计算机科学与技术系课程设计报告2014 ～2015 学年第学期课程数据结构与算法课程设计名称内部排序算法比较学生姓名学号专业班级指导教师2015 年1 月【课题22、】内部排序算法比较一、问题分析和任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

根据对本设计任务要求的理解和分析，按以下两点问题进行分析：题目要求对十种排序算法进行比较，比较的主要内容是关键字的比较次数和移动次数，其中待排序数用。

二、数据结构的选择和概要设计为了实现十种排序算法，产生的随机数用顺序表存储比较方便。

顺序表数据类型（存储结构）描述如下：typedef int KeyType;struct rec{KeyType key;};typedef rec sqlist[N];：(1) void gensort(int b[],int n)起泡排序(2) void insertsort(sqlist b,int n)插入排序(3) void so(sqlist num,int n)折半插入排序(4) void shellsort(sqlist b,int n)希尔排序(5) void gentsort(int b[],int n)选择排序(6) void output(sqlist b,int n)快速排序(7) void sort3(sqlist nu,int n) //2-路插入排序(8) void Merge(sqlist a, sqlist b, int low, int mid, int high)二路归并排序(9) void MergePass(sqlist a, sqlist b, int n, int lenth)一趟归并排序(10) void MergeSort(sqlist a, int n) //进行二路归并(11) void sift(sqlist r,int s,int m) 堆排序(12) void init(int a[])//随机生成N个整数三、详细设计和编码在整个课程设计中，要求实现要求的功能，必须要有主函数，并通过主函数调用各功能子模块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。

数据结构课程设计报告几种排序算法的演示1、需求分析:运行环境:Microsoft Visual Studio 20052、程序实现功能:3、通过用户键入的数据, 经过程序进行排序, 最后给予数据由小到大的输出。

排序的方式包含教材中所介绍的几种常用的排序方式：直接插入排序、折半插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。

每种排序过程中均显示每一趟排序的细节。

程序的输入:输入所需排序方式的序号。

输入排序的数据的个数。

输入具体的数据元素。

程序的输出:输出排序每一趟的结果, 及最后排序结果1、设计说明:算法设计思想:a交换排序（冒泡排序、快速排序）交换排序的基本思想是: 对排序表中的数据元素按关键字进行两两比较, 如果发生逆序（即排列顺序与排序后的次序正好相反）, 则两者交换位置, 直到所有数据元素都排好序为止。

b插入排序（直接插入排序、折半插入排序）插入排序的基本思想是: 每一次设法把一个数据元素插入到已经排序的部分序列的合适位置, 使得插入后的序列仍然是有序的。

开始时建立一个初始的有序序列, 它只包含一个数据元素。

然后, 从这个初始序列出发不断插入数据元素, 直到最后一个数据元素插到有序序列后, 整个排序工作就完成了。

c选择排序（简单选择排序、堆排序）选择排序的基本思想是: 第一趟在有n个数据元素的排序表中选出关键字最小的数据元素, 然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素, 依次重复, 每一趟（例如第i趟, i=1, …, n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素, 作为有序数据元素序列的第i个数据元素。

等到第n-1趟选择结束, 待排序数据元素仅剩下一个时就不用再选了, 按选出的先后次序所得到的数据元素序列即为有序序列, 排序即告完成。

d归并排序（两路归并排序）1、两路归并排序的基本思想是: 假设初始排序表有n个数据元素, 首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项）, 先做两两归并, 得n/2上取整个长度为2的归并项（如果n为奇数, 则最后一个归并项的长度为1）；再做两两归并, ……, 如此重复, 最后得到一个长度为n的有序序列。

`课题：内部排序算法比较…第一章问题描述排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。

比较的结果用一个直方图表示。

第二章系统分析界面的设计如图所示：!|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|~请选择操作方式：如上图所示该系统的功能有：（1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。

（2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。

（3）选择0 打印“谢谢使用！！”退出系统的使用！！、第三章系统设计（I）友好的人机界面设计：（如图所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|：（）（II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|；请选择操作方式：（用户在此输入操作方式）（）（III）系统采用定义结构体数组来存储数据。

《数据结构》课程设计报告排序算法的实现与比较设计内容及要求编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。

将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。

概述在本设计课题中，我们将对常见的5中排序算法——插入、希尔、快速、堆排序、归并排序进行各种情况下的比较，如待排数据为顺序、逆序或随机的情况下，各个算法对于特定数据的性能。

基于此点考虑，在程序中选择采用以毫秒为单位的执行时间来衡量算法对特定数据的性能高低。

本文将主要介绍《排序之谜》程序（以下简称“程序”）的数据结构的设计、功能设计以及相关技术讨论等。

本程序在Microsoft Windows Server 2003/Microsoft Visual C++ 2005的命令行编译器cl.exe环境编译下通过。

分发包说明程序分发包中将包含以下文件，其用途分别如表格1所示。

数据结构设计主程序数据结构主程序中采用两个整型数组input_array和output_array，其长度均为10000，分别作为待排序数据和已排序数据的存放空间，并设置一整型数组sort_time用来存放5个算法的执行时间。

之所以这样设计，是因为所有的用户定义函数都完全按照既定的“标准”设计实现，使得整个程序的可伸缩性大大增强。

排序算法的设计实现程序中的全部5中排序算法均按照标准化的函数名、返回值和形参表设计，其形式为：1实现。

插入排序插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。

快速排序1参见：参考资料[2]和[3]。

快速排序是对冒泡法排序的一种改进。

它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录均比另一部分记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

归并排序归并排序的核心操作是将一位数组中前后两个相邻的有序序列归并为一个有序序列，其实现如下：并为相邻的有序序列，依次递归的执行下去，最终归并为一个有序序列。

排序算法比较专业班级：XXX学号：XXX姓名：XXX指导教师：XXX课程设计时间：XXX计算机科学与技术专业数据结构课程设计任务书学生姓名XXX 专业班级XXX 学号XXX 题目排序算法比较课题性质工程设计课题来源XXX指导教师XXX同组姓名XXX主要内容1.输入一个大于0的整数，生成一组无序数列2.设计冒泡排序，快速排序，插入排序，选择排序，希尔排序，归并排序的子函数，对生成的无序数列进行排序3.设计主函数对各排序算法子函数进行调用4.输出各排序算法排序的移动次数和时间任务要求1．研究各种排序算法的数据存储方式2．实现各种排序的主要算法3．分析算法的运行效率4．具有良好的运行界面5．算法具有良好的健壮性6．按要求撰写课程设计报告和设计总结。

参考文献1．《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社，1997. 2．《Visual C++实用教程（第一版）》，张荣梅、梁晓林，冶金工业出版社，2004.审查意见指导教师签字：教研室主任签字： 年 月 日1 需求分析对一组无序数运用各种算法进行排序，并返回排序移动次数和运行时间2 概要设计3 运行环境（软、硬件环境）1) 硬件：PC 机main 生成无序数组进行冒泡排序 进行希尔排序 进行选择排序 进行快速排序 进行归并排序输出移动次数和时间2)操作系统：Windows 2000/XP/20033)编译环境：Visual C++6.04 开发工具和编程语言开发工具：VISCALL c++6.0；编程语言：C语言。

5 详细设计1.声明数据类型2.编写addlist函数生成随机无序数组3.编写qipao函数实现冒泡排序，并输出排序移动次数和时间4.编写insertSort函数实现插入排序，并输出排序移动次数和时间5.编写SelectSort函数实现选择排序，并输出排序移动次数和时间6.编写xierSort函数实现希尔排序，并输出排序移动次数和时间7.编写MergeSort函数实现归并排序，并输出排序移动次数和时间8.编写Main函数对子函数进行调用6 调试分析在调试过程中出现的一些问题：1、输入语句中没有加取地址符号&2、误把取地址运算符&当作逻辑与&&3、误把赋值=当恒等==4、条件语句（if）后误加分号5、循环语句中改变了循环变量6、作为输出结果的变量没有赋初值7.中英文输入切换导致符号错误7 测试结果8 参考文献[1]谭浩强，C程序设计题解与上机指导（第3版），清华大学出版社，2005.7.[2][美]Harvey M. Deitel，Paul J. Deitel 著，聂雪军，贺军译，C程序设计经典教程（第4版），清华大学出版社，2006。

《数据结构》课程设计实验报告题目：排序算法的实现与比较目录一．设计内容和要求----------------------------------2 二．算法思想-------------------------------------------2 三．程序结构-------------------------------------------3 四．使用说明-------------------------------------------4 五．测试结果-------------------------------------------5 六．收获与体会----------------------------------------6一．设计内容和要求设计内容：排序算法的实现与比较要求：编程实现希尔、快速、堆排序、归并排序算法，并利用程序统计每种算法的执行时间。

要求随机产生10000、50000、100000、200000个待排数据存入磁盘文件，从磁盘文件读入待排数据进行排序，并将排序结果写入另一个文件中。

二．算法思想在本课题中，对常见的4 中排序算法希尔、快速、堆排序、归并排序进行实现，并根据待排数据个数的不同来对各种排序算法的执行时间进行比较，从而比较出在不同的情况下各排序算法的性能。

1.希尔排序希尔排序是对直接插入排序的一种改进，它的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

2.快速排序快速排序是对气泡排序的一种改进，其基本思想是：首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。

3.堆排序堆排序是简单选择排序的一种改进，其基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大值即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录。

《数据结构》课程设计报告题目: 排序算法的比较目录一、课程设计名称 (Ⅲ)二、使用工具软件 (Ⅲ)三、目的意义 (Ⅲ)四、基本要求 (Ⅲ)五、实验歩骤 (Ⅲ)六、运行结果 (Ⅺ)七、得意之处 (XIV)八、创意的技术实现 (XV)九、目前存在的问题 (XV)十、设计实验过程中的自我感受 (XV)十一、主要参考资料 (XV)一、课程设计名称：排序算法的比较二、使用工具软件：Microsoft Visual C++6.0三、目的意义：1.掌握各种排序算法（直接出入排序、冒泡排序、快速排序、简单选择排序）的思路核心，比较他们之间的优劣2.全面提高学生的程序设计、开发能力四、基本要求：1．任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间2．友好性：界面要友好，输入有提示，尽量展示人性化 3．可读性：源程序代码清晰、有层次4．健壮性：用户输入非法数据时，系统要及时给出警告信息五、实验歩骤：#include"iostream.h"#include"stdio.h"#include"stdlib.h"#include"time.h"long count = 0;#define MAXSIZE 100000typedef long keyType;typedef struct{keyType key;}RcdType;typedef struct{RcdType r[MAXSIZE+1];int length;}SqList;SqList L;void Swap(RcdType &r1,RcdType &r2){RcdType t=r1;r1=r2;r2=t;}void print(SqList L){for(long i =1;i<=L.length;i++)cout<<L.r[i].key<<"\t";cout<<endl;}/*************************直接插入排序*************************/long InsertionSort ( SqList &L ) {// 对顺序表 L 作直接插入排序count =0;for (long i=2; i<=L.length; ++i ) //n-1趟 if (L.r[i].key < L.r[i-1].key) {L.r[0] = L.r[i]; // 设置哨兵for (long j=i-1; L.r[0].key < L.r[j].key; -- j ){count++;L.r[j+1] = L.r[j]; } // 记录向后顺移L.r[j+1] = L.r[0]; // 插入到正确位置 }return count;}/*************************冒泡排序*************************/long BubbleSort(SqList &L){int flag = 1;count = 0;for (long i=1;i<L.length;i++){//n-1趟排序 count++;flag = 0;for (long j=1;j<=L.length-i;j++)//每一趟里n-i 次比较if (L.r[j+1].key < L.r[j].key) Swap(L.r[j], L.r[j+1]);//交换L.r[i]与L.r[j]}return count;}/*************************快速排序*************************/long Partition (SqList &L, long low, long high) {L.r[0] =L.r[low];count++;keyType pivotkey = L.r[0].key; // 枢轴while (low < high) {//循环结束时low==high+1while(low<high && L.r[high].key>=pivotkey)--high; //从右向左搜索关键字比枢轴小的记录并控制越界if(low<high) {L.r[low++] = L.r[high]; count++;} //比枢轴记录小的移到左部while (low<high && L.r[low].key<=pivotkey)++low; //从左向右搜索关键字比枢轴大的记录并控制越界if(low<high) {L.r[high--] = L.r[low];count++;} //比枢轴记录大的移到右部}L.r[low] = L.r[0];count++;return low; //low==high+1}void QSort(SqList &L, long low, long high) {// 对记录序列L.r[low..high]进行快速排序if (low < high) { // 记录个数大于1long pivotloc = Partition(L,low,high);// 对 L.r[low..high] 进行一次划分QSort(L, low, pivotloc-1); //对左部进行快速排序QSort(L, pivotloc+1, high); //对右部进行快速排序}}long QuickSort(SqList &L){count =0;QSort(L,1,L.length);return count;}/*************************简单选择排序*************************/long SelectMinKey(SqList &L,int i){ long j=i;for( long k=i+1;k<=L.length ; k++)if ( L.r[k].key <L.r[j].key) j=k; return j;}long SelectSort (SqList &L) {count = 0;for (long i=1; i<L.length; ++i) {// 选择第 i 小的记录，并交换到位count++;long j = SelectMinKey(L, i);//在L.r[i..L.Length]中选择关键字最小的记录if (i!=j) Swap(L.r[i],L.r[j]);// 与第 i 个记录交换}return count;}/*************************操作选择函数*************************/void operate(){time_t start,end;double dif;long degree;SqList L1;char ch;cout<<"请选择排序算法："; cin>>ch;switch(ch){case 'a':{for(long i = 1;i<=L.length;i++) L1.r[i] = L.r[i]; L1.length = L.length;time(&start);degree = InsertionSort(L1);time(&end);dif = difftime(end,start);cout<<"直接插入排序所用时间：" << dif << "秒\n";cout<<"直接插入排序移动次序：" << degree << endl;print(L1);cout<<endl;break;}case 'b':{for(long i = 1;i<=L.length;i++) L1.r[i] = L.r[i]; L1.length = L.length;time(&start);degree = BubbleSort(L1);time(&end);dif = difftime(end,start);cout<<"冒泡排序所用时间：" << dif << "秒\n";cout<<"冒泡排序移动次序：" << degree << endl;print(L1);cout<<endl;break;}case 'c':{for(long i = 1;i<=L.length;i++) L1.r[i] = L.r[i]; L1.length = L.length;time(&start);degree = QuickSort(L1);time(&end);dif = difftime(end,start);cout<<"快速排序所用时间：" << dif << "秒\n";cout<<"快速排序移动次序：" << degree << endl;print(L1);cout<<endl;break;}case 'd':{for(long i = 1;i<=L.length;i++) L1.r[i] = L.r[i]; L1.length = L.length;time(&start);degree = SelectSort(L1);time(&end);dif = difftime(end,start);cout<<"简单选择排序所用时间：" << dif << "秒\n";cout<<"简单选择排序移动次序：" << degree << endl;print(L1);cout<<endl;break;}case 'q': exit(0); //退出default:{cout<<"您的输入错误，请输入正确的操作！"<<endl;break;}}}/*************************主函数*************************/void main(){cout<<"\n 欢迎进入排序算法 "<<endl;cout<<"\n 设计者：樊盼盼 "<<endl;cout<<"\n 班级：计科1411 "<<endl;cout<<"\n 指导老师：王宏杰 "<<endl;cout<<"\n 设计时间：2016年6月 \n "<<endl;cout<<"===================================== ==========================================="<<endl ;cout<<" a --- 直接插入排序 "<<endl;cout<<" b --- 冒泡排序 "<<endl;cout<<" c --- 快速排序 "<<endl;cout<<" d --- 简单选择排序 "<<endl;cout<<" q --- 退出程序 \n"<<endl;cout<<"===================================== ==========================================="<<endl ;cout<<"\n请输入要产生的随机数的个数：";long n;cin>>n;srand((unsigned long)time(NULL));for(long i = 1;i<=n;i++) L.r[i].key = rand()%n;L.length = n;print(L);for(int j=0;j<=7;j++) operate();}六、运行结果：点击执行出现的第一个界面输入要产生的随机数的个数，得到如下请选择直接插入排序算法，得到的结果如下选择冒泡排序算法选择快速排序算法选择简单选择排序算法选择去退出程序七、得意之处：输入相应的序号可以跳转到不同的程序去调用不同的排序方法去执行，计算出不同的运行次数。