下载文档原格式
数据结构课程设计各种排序算法比较课程设计课程：数据结构题目：排序算法比较专业班级：姓名：学号：设计时间：指导教师：—、设计题目排序算法比较二、运行环境（软、硬件环境）操作系统windows运行环境vc6.0三、算法设计的思想大架构采用模块化编程的思想，将每个不同的功能分别写成不同的子程序，分别进行封装构成各个小的模块，最后将各个模块组合起来。
在每个子程序的编写过程中特事特办面对不同的预想功能采取不同的数据结构不同的算法实现。
总体算法思想为按功能分块，依照预想功能实现顺序拼装。
具体思想请见流程图。
四、流程图程序编写流程图开始编写各个子算法子函数，和时间选择函教，既革单结束算法流程图五、算法设计分析程序总体采用模块化设计，程序间经过传参和调用进行有机组合。
这样的总体布局将将各个功能隔离开来，每个模块负责每个模块的功能，使得程序的布局简单明了。
且子程序只有在被调用时才会运行大大节约系统资源减少了运算时间。
同时由于功能的隔离使得程序的扩展性大大提高，无论程序将要任何改动时，都会方便很多。
六、源代码#include<stdio.h>#include<time.h>#include<stdlib.h>int a[30000];int choice;int choice1;struct xlx{int key;int link;} aa[30000];int aaa[300000];void main1();************************* 直接插入排序函数***********************void direct(int a[])(printf（"\n现在使用直接插入排序法进行排序:\n"）; int i,j,w;for(i=0;i<30000;i++)(for(j=i;j>=0;j--)(if(a[j]>=a[j+1])(w=a[j];a[j]=a[j+1];a[j+1]=w;}}}}************************* 冒泡排序函数*************************/void bubble_sort(int a[])(printf("\n下面使用冒泡排序法进行排序："); int i,j,w;for(i=0;i<30000;i++)for(j=0;j<30000-i;j++)if(a[j]>a[j+1])(w=a[j];a[j]=a[j+1];************************* 选择排序****************************/ void choices_sort(int a[])( printf("\n现在使用选择排序法进行排序：\n");int i,j,k,t;for(i=0;i<30000;i++)(k=i;for(j=i+1;j<30000;j++)if(a[k]>a[j])k=j;t=a[i];a[k]=t;}}/*****************************************************/quick(int first,int end,int L[])(int left=first,right=end,key;key=L[first];while(left<right)( while((left<right)&&(L[right]>=key)) right--;if(left<right)L[left++]=L[right];while((left<right)&&(L[left]<=key)) left++;if(left<right)L[right--]=L[left];}L[left]=key;return left;void quick_sort(int L[],int first,int end)(int split;if(first<end)( split=quick(first,end,L);quick_sort(L,first,split-1);quick_sort(L,split+1,end);} }************************** 堆排序***************************** void sift(int *x, int n, int s)(int t, k, j;t = *(x+s); 偕存开始元素*/k = s; 斤始元素下标*/j = 2*k + 1; 佑子树元素下标*/while (j<n)(if (j<n-1 && *(x+j) < *(x+j+1)) /* 判断是否满足堆的条件：满足就继续下一轮比较，否则调整。
实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。
三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。
四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。
数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。
内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。
本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
冒泡排序是一种简单直观的排序算法。
它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。
这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。
因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。
插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。
选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
以此类推，直到全部待排序的数据元素排完。
选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。
快速排序是一种分治的排序算法。
它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。
快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。
然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。
归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。
合肥学院计算机科学与技术系1、问题分析和任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。
我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。
待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。
2、数据结构的选择和概要设计一．可能排序表的抽象数据类型定义：ADTOrderableList｛数据对象：D=｛|∈IntegerSet，i=1，2，……，n，n≥0｝数据关系：R1=｛<,|,∈D,i=2,……n｝基本操作：InitList（n）操作结果：构造一个长度为n，元素值依次为1，2，……，n的有序表。
RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0≤d≤8）级随机打乱。
d为0时表不打乱，d越大，打乱程度越高。
RecallList（）操作结果：恢复最后一次用RandomizeList随机大乱的可排序表。
ListLength（）操作结果：返回可排序的长度。
ListEmpty（）操作结果：若可排序表为空表，则返回True，否则返回False。
BubbleSort（&c，&s）操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。
InsertSort（&c，&s）操作结果：进行插入排序，返回关键字比较次数c和移动次数s。
SelectSort（&c，&s）操作结果：进行选择排序，返回关键字比较次数c和移动次数s。
QuickSort（&c，&s）操作结果：进行快速排序，返回关键字比较次数c和移动次数s。
数据结构课程设计报告几种排序算法的演示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的有序序列。
数据结构课程设计报告题目：各种内排序性能比较学生姓名：学号：班级：指导教师：2011-6-13目录1、需求分析说明 (2)1.1所需完成的任务及要求1.2程序实现的功能2、总体设计 (3)2.1 总体设计说明2.2 总体流程图2.3各主程序详细流程图3、详细设计 (7)3.1使用的算法思想3.2各个算法的效率简析4、实现部分 (8)4.1程序算法的代码5、程序测试 (15)5.1程序运行的主界面5.2 各算法运行界面6、总结 (18)1、需求分析说明排序是数据处理中经常遇到的一种重要操作。
然而排序的算法有很多，各有其优缺点和使用场合。
本程序的设计的主要目的是通过比较各种内部排序（包括：插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。
达到在实际应用中选择合适的方法消耗最短的时间完成排序。
1.1所需完成的任务及要求任务：1)用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；2)输入的数据形式为任何一个正整数，大小不限。
要求：排序后的数组是从小到大的；1.2程序实现的功能（1）使用随机函数实现数组初始化，生成多组元素个数不同的数组；（2）用列表打印出每种排序下的各趟排序结果；（3）打印使用各种排序算法以后元素比较和交换的次数；（4）设计合理的打印列表来打印。
2、总体设计（从总体上说明该题目的框架，用文字和图表说明）2.1 总体设计说明采用插入气泡，选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较次数的统计。
对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块；2.2 总体流程图2.3 各主程序详细流程图①主函数流程图：3、详细设计3.1 使用的算法思想（1）对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用；（2）在插入法时，其算法思想是：将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可；（3）在起泡法时，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数；（4）对于选择法，其排序思想是:从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元素的位置，则排序完成；（5）对于快速法，其算法思想是：一般取数组中的第一个元素为基准，通过一趟排序将待排序元素分为左右两个子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后将左右两个序列按照与此相同的原理进行排序，直至整个序列有序为止，排序完成。
《数据结构与算法设计》课程设计报告题目：排序算法比较学生姓名：汪洪学号： 201120181805班级： 1121822指导教师：周华清2013年1月10日目录需求分析·3总体设计·4详细设计·5类的设计·5现实部分·8随机数赋值·8结果输出·8直接插入排序·9冒泡排序·10选择排序·11快速排序·13堆排序·15二路归并排序·18程序测试·21总结·25一．需求分析本程序主要为了实现对各排序算法的性能比较。
主要包括对直接插入排序，冒泡排序，选择排序，快速排序，堆排序二路归并排序六种排序算法在时间复杂度上的性能比较。
基于此目的需要设定一个顺序表来产生一组数据，本程序用了一个长度为30000的long int型数组并用了以时间为随机种子产生了一组数组。
用六个模块来实现各种排序功能并在各模块中完成计算排序所用的时间。
并用一个数组保存各种排序所用的时间。
为了比较各种排序的在时间上的优劣性将各个排序所用的时间进行比较并输出结果！二．总体设计三．详细设计1.类的设计本程序功能只是为了比较各种排序算法在时间上的优劣。
所以可以用一个类来完成的有的操作，固本程序只需定义一个类。
为实现本程序功能定义一个类其中包括了一个长度300000的数组。
并且为了实现各种排序功能应当设计功能函数分别实现各种类型的排序和排序后的结果。
以下对这个类进行详细说明。
类名：：sortrather数据成员：long int a[N] 其中N为一个全局常量其值为30000，该成员用来保存一个用于保存一组数据用于排序。
Long int time[6]该数组用于保存各种排序所用的时间，以便对种种排序所用时间进行比较。
成员函数：1.void pubction（）实现功能：本函数的的作用是给数据成员 a[N]进行随机赋值。
****课程设计报告题目：各种内部排序性能比较学生姓名：彭伟奇学号： 1021112417班级：10211124指导教师：高永平2012年6 月15 日一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、实验要求任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。
输出的形式：数字大小逐个递增的数列。
功能要求：给出多组不同元素个数的输入数据(可考虑用随机函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。
每个排序法结束时应打印出其元素比较的次数和交换的次数。
此程序需将结果用列表打印，一定要将其打印结果排列好。
三、程序源代码#include "stdlib.h"#include"stdio.h"#include"time.h"#define MAXSIZE 200typedef int KeyType;typedef struct //定义存储记录关键字及其他信息的结构体{ KeyType key;char other;}RedType;typedef struct //定义存储所有记录的结构体{ RedType r[MAXSIZE+1];int length;}SqList;typedef struct{int move; /*记录数据移动次数*/int comp; /*记录数据比较次数*/}Recode;int dlta[5]={31,15,7,3,1}; //初始化希尔排序的增量序列int num[10]={0}; //记录每个排序方法的移动次数和比较次数int flag=0; //标记变量//利用产生的随即数模拟用户输入的数据class sort{public:void select_sort(SqList L);void Zhijie(SqList L) ;void ShellInsert(SqList *L,int dk,Recode *r);void ShellSort(SqList L,int dlta[],int t) ;void Maopao(SqList L);int Partition(SqList *L,int low,int high,Recode *r); void QuickSort(SqList L) ;protected:int dk,dlta[5],t,low,high;};void create(SqList *L,int length){ int i;srand(time(0));L->length=length;for(i=1;i<=L->length;i++){L->r[i].key=rand()%1000;L->r[i].other=rand()%5;}}/*输出元素*/void visit(SqList L){int i;printf("\n");for(i=1;i<=L.length;i++)printf("%4d%2c",L.r[i].key,L.r[i].other);printf("\n");}/*简单选择排序*/void select_sort(SqList L){ Recode r;p =0;r.move =0;int i,j,k;RedType t;for (i=1;i<L.length;i++){ j=i;for (k=i+1;k<=L.length;k++){ p++;if (L.r[j].key>L.r[k].key){j=k;}}if (i!=j){t=L.r[j];L.r[j]=L.r[i];L.r[i]=t;r.move =r.move +3;}}if(!flag){ printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("简单选择排序后的结果：");visit(L);}else{num[0]=r.move;num[1]=p;}}//直接插入排序void Zhijie(SqList L){ Recode r;p =0;r.move =0;int j;for(int i=2;i<=L.length;++i){ p ++;if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i]; //复制为哨兵L.r[i]=L.r[i-1];r.move=r.move +2;for(j=i-2;L.r[0].key < L.r[j].key;--j){L.r[j+1]=L.r[j]; //记录后移r.move ++;p ++;}L.r[j+1]=L.r[0]; //插入到正确位置r.move ++;}}if(!flag){printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("直接插入排序后的结果：");visit(L);}else{num[2]=r.move;num[3]=p;}}void ShellInsert(SqList *L,int dk,Recode *r){ int i,j;for(i=dk+1;i<=L->length ;++i){ r->comp ++;if(L->r[i].key<L->r[i-1].key){ L->r[0]=L->r[i]; //暂存r->move ++;for(j=i-dk;j>0&&(L->r[0].key < L->r[j].key);j-=dk){ L->r[j+dk]=L->r[j]; //记录后移r->move ++;r->comp ++;}L->r[j+dk]=L->r[0]; //插入到正确位置r->move ++;}}}void ShellSort(SqList L,int dlta[],int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序。
《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。
数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小void Display(LinkList* L) //显示输出函数void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。
实验报告（2010 / 2011 学年第 2 学期）课程名称数据结构——使用C++语言描述实验名称各种内排序算法的实现及性能比较实验时间2011年5月27日指导单位计算机科学与技术系指导教师学生姓名班级学号学院(系)专业一．实验目的和要求内容：验证教材的各种内排序算法。
分析各种排序算法的时间复杂度。
要求：使用随机数产生器产生大数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。
二．实验环境（实验设备）Visual C++三．实验原理及内容单选择排序"<<endl;接插入排序"<<endl;泡排序"<<endl;速排序"<<endl;路合并排序"<<endl;排序"<<endl;出"<<endl;cout<<"PS：测试用的数组元素为"<<SIZE<<"时间为重复运行"<<TIMES<<"次的时间（包括了产生数据与析构的时间）"<<endl;this->switcha();}template <class T>void Menu<T>::childmenu(){cout<<"--------------------------------------------------------"<<endl;cout<<"1.最好情况"<<endl;cout<<"2.最坏情况"<<endl;cout<<"3.平均情况"<<endl;cout<<"4.返回主菜单"<<endl;cin>>b;if(b==4)this->printmenu();}template<class T>void Menu<T>::childmenu2(){cout<<"--------------------------------------------------------"<<endl;cout<<"1.原始算法"<<endl;cout<<"2.改进算法"<<endl;cout<<"3.返回主菜单"<<endl;cin>>c;if(c==3)this->printmenu();}template <class T>void Menu<T>::switcha(){<<endl;return 0;}/*ok--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok1简单选择排序直接用随机数据测试ok用时：请按任意键继续. . .--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok2直接插入排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单1ok用时：0请按任意键继续. . .直接插入排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单2ok用时：请按任意键继续. . .直接插入排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单3ok用时：请按任意键继续. . .直接插入排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单4--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok3冒泡排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单1ok用时：请按任意键继续. . .冒泡排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单2ok用时：请按任意键继续. . .冒泡排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单3ok用时：请按任意键继续. . .冒泡排序--------------------------------------------------------1.最好情况2.最坏情况3.平均情况4.返回主菜单4--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok4--------------------------------------------------------1.原始算法2.改进算法3.返回主菜单1原始快速排序直接用随机数据测试ok用时：请按任意键继续. . .--------------------------------------------------------1.原始算法2.改进算法3.返回主菜单2改进的快速排序直接用随机数据测试ok用时：请按任意键继续. . .--------------------------------------------------------1.原始算法2.改进算法3.返回主菜单3--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok5合并排序直接用随机数据测试ok用时：请按任意键继续. . .--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok6堆排序直接用随机数据测试ok用时：请按任意键继续. . .--------------------------------------------------------内排序测试系统--------------------------------------------------------1.简单选择排序2.直接插入排序3.冒泡排序4.快速排序5.两路合并排序6.堆排序7.退出PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间）ok7Press any key to continue*/四．实验小结（包括问题解和解决方法、心得体会、意见与建议等）通过本次实验对教材上的各种内排序算法进行了逐一验证。
数据结构课程设计报告题目：各种内排序性能的比较学生姓名：学号：班级：指导教师：2012-6-10实现部分各个核心算法的代码：#include <iostream>#include <ctime>using namespace std;const int M=100;int compareN=0,changeN=0; //快速排序中元素比较的次数和交换的次数int compareN1=0,changeN1=0,K=0; //合并排序中元素比较的次数和交换的次数void display(int r[], int n){for(int i=0;i<n;i++){cout.width(4);cout<<r[i];}cout<<endl<<endl;}void insertsort(int r[],int n) //直接插入法排序//待排序元素用一个数组r表示，数组有n个元素{int a=0,b=0,k=1;//a表示元素比较的次数，b表示元素交换的次数,k 表示趟数cout<<"插入排序的每一次的结果如下："<<endl<<endl;cout<<"初始状态:";display(r,n);for(int i=1;i<n;i++) //i表示插入次数，共进行n-1次插入{int temp=r[i]; //把待排序元素赋给tempint j=i-1;while((j>=0)&&(temp<r[j])){a++;r[j+1]=r[j];j--; //顺序比较和移动}a++;r[j+1]=temp;b++;cout<<"第"<<k<<"趟: ";k++;display(r,n);}cout<<"\t\t\t\t -->元素比较次数为"<<a<<"次"<<endl;cout<<"\t\t\t\t -->元素交换次数为"<<b<<"次"<<endl;}void bubblesort(int r[],int n) //冒泡排序{int a=0,b=0,k=1,flag=1; //当flag=0时停止排序(flag用于判断元素是否进行过交换)cout<<"冒泡排序的每一次的结果如下："<<endl<<endl;cout<<"初始状态:";display(r,n);for(int i=1;i<n;i++) //i表示趟数，最多n-1趟{flag=0; //开始时元素未交换for(int j=n-1;j>=i;j--){a++;if(r[j]<r[j-1]){//发生逆序int t=r[j];r[j]=r[j-1]; //元素后移r[j-1]=t;flag=1; //交换，并标记发生了交换b++;}flag=1;if(flag==0)break;}cout<<"第"<<k<<"趟: ";k++;display(r,n);}cout<<"\t\t\t\t -->元素比较次数为"<<a<<"次"<<endl;cout<<"\t\t\t\t -->元素交换次数为"<<b<<"次"<<endl;}void selectsort(int r[],int n)//直接选择排序{int i,j,m,t,a=0,b=0,k=1;cout<<"选择排序的每一次的结果如下："<<endl<<endl;cout<<"初始状态:";display(r,n);for(i=0;i<n-1;i++){m=i;for(j=i+1;j<n;j++)if(r[j]<r[m]) //从r[0]~r[n-1]中找到最小的{a++;m=j;}if(m!=i) //找到最小的后与前面的交换，以此类推{t=r[i];r[i]=r[m];r[m]=t;b++;}cout<<"第"<<k<<"趟: ";k++;display(r,n);}cout<<"\t\t\t\t -->元素比较次数为"<<a<<"次"<<endl;cout<<"\t\t\t\t -->元素交换次数为"<<b<<"次"<<endl;}//递归形式的快速排序void quicksort(int r[],int left,int right,int n)//快速排序,递归调用，使用全局变量，结果在main函数中实现{int i=left,j=right,k=1;int temp=r[i];while(i<j){while((r[j]>temp)&&(j>i))//同时满足两个条件时才会执行j--,即向前移动j,并且如果没有发现r[j]中没有比temp小的则当i=j时停止{compareN++; //compareN用于快速排序中计算元素比较的次数j=j-1;}if(j>i) //r[j]中存在比temp小的值{r[i]=r[j];i=i+1;changeN++; //changeN用于快速排序中计算元素交换的次数cout<<"第"<<K<<"趟: ";K++;display(r,n);}while((r[j]<=temp)&&(j>i)){compareN++;i=i+1;}if(i<j){changeN++;r[j]=r[i];j=j-1;}}r[i]=temp; //一次划分得到基准值的正确位置if(left<i-1)quicksort(r,left,i-1,n); //递归调用左子区间if(i+1<right)quicksort(r,i+1,right,n); //递归调用右子区间}//合并排序void merge( int r[],int a[],int s,int m,int t)//将两个子区间人r[s]~r[m]和r[m+1]~r[t]合并，结果存入a{int i,j,temp;i=s;j=m+1;while((i<=m)&&(j<=t)){compareN1++;if(r[i]>=r[j]){changeN1++;temp=r[j];for(int k=j-1;k>=i;k--){r[k+1]=r[k];}r[i]=temp;j++;}else{i++;}}for(int l=s;l<=t;l++)a[l]=r[l];}void mergepass(int r[],int a[],int n,int c)//对r数组做一趟归并，结果存入a数组中，n为元素个数，c为区间长度{int i,j;i=0;while(i+2*c-1<=n-1){ //长度均为c的两个区间合并成一个区间merge(r,a,i,i+c-1,i+2*c-1);i+=2*c;}if(i+c-1<n) //长度不等的两个区间合并成一个区间merge(r,a,i,i+c-1,n-1);else //仅剩一个区间时直接复制到a 中for(j=i;j<=n-1;j++)a[j]=r[j];}void mergesort(int r[],int n) //二路归并{int c=1,i=0,k=1;int a[M];cout<<"二路归并排序的每一次的结果如下："<<endl<<endl;cout<<"初始状态:";display(r,n);while(c<n){mergepass(r,a,n,c); //一次合并，结果存入a中i=i+1;cout<<"第"<<k<<"趟: ";k++;display(r,n);c*=2;mergepass(a,r,n,c); //再次合并，结果存入r中i=i+1;cout<<"第"<<k<<"趟: ";k++;display(r,n);c*=2;}}void menu(){cout<<""<<endl<<endl;cout<<" 各种内排序性能比较"<<endl;cout<<" ----------------------------- "<<endl;cout<<""<<endl;cout<<" 1. 插入法"<<endl;cout<<" 2. 冒泡法"<<endl;cout<<" 3. 选择法"<<endl;cout<<" 4. 快速法"<<endl;cout<<" 5. 合并法"<<endl;cout<<" 0. 退出"<<endl;cout<<" ------------------------------ "<<endl<<endl;cout<<"请选择您要排序的方法: ";}int main(){int k; //K表示排序的元素个数int *R1 =new int [20]; //因为是地址传递，所以要用到两个数组int *R2=new int [20];cout<<"系统将随机产生数组元素请输入要产生的元素个数K: ";cin>>k;cout<<endl;cout<<"以下是随机生成的数组:"<<endl;for(int i=0;i<k;i++){R2[i]=rand()%100;}display(R2,k);do{for(int i=0;i<k;i++) //每次执行do...while语句时，先将R2赋给R1，保证每次排序的数组是随机的R1[i]=R2[i];menu();int select;cin>>select;switch (select){case 0:delete [] R1;delete [] R2;exit(0);case 1:insertsort(R1,k); //插入排序break;case 2:bubblesort(R1,k); //冒泡排序break;case 3:selectsort(R1,k); //选择排序break;case 4:{cout<<"快速排序的每一次的结果如下："<<endl<<endl;if(compareN!=0)compareN=0;if(changeN!=0)changeN=0;quicksort(R1,0,k-1,k); //快速排序cout<<"\t\t\t\t -->元素比较次数为"<<compareN<<"次"<<endl;cout<<"\t\t\t\t -->元素交换次数为"<<changeN<<"次"<<endl;break;}case 5:{if(compareN1!=0)compareN1=0;if(changeN1!=0)changeN1=0;mergesort(R1,k); //合并排序cout<<"\t\t\t\t -->元素比较次数为"<<compareN<<"次"<<endl;cout<<"\t\t\t\t -->元素交换次数为"<<changeN<<"次"<<endl;break;}default:{cout<<"输入错误!请重新输入...."<<endl;break;}}}while(1);return 0;}程序测试程序运行的主界面（数组下标以及数组中的各个元素均由随机函数产生）①插入法各算法运行界面②冒泡法③选择法④快速法⑤合并法总结这次课程设计虽然做得很辛苦，但很有成就感；当看到自己的程序完成运行成功，那种感觉比什么都爽，可能那就是成就感吧，呵呵。
