内部排序演示C++-课程设计.doc

内部排序演示C+-课程设计【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。【基本要求】(1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。（gettickcount()）【数据结构描述】输入一个无序数组，分别使用内部排序的几种方法：bubble_sort(n,A);冒泡排序，insertion_sort(n,A);插入排序selection_sort(n,A);选择排序quick_sort(n,A);快速排序shell_sort(n,A);希尔排序求出分别的比较次数和移动次数。【主要算法流程描述】源程序代码#include #define N 100/定义数组最大为100const int t=3;/定义希尔排序次数int dt=4,3,1;/定义希尔排序比较量int qmt;/快速排序的移动次数int qct;/快速排序的比较次数 void output(int n,int a,int ct,int mt)/内部排序中调用的输出函数 int i; printf(n排序结果:); for( i=0;in;i+) printf(%d ,ai);/输出各排序完成的数组 printf(n比较次数:%dn,ct);/输出各排序比较次数 printf(移动次数:%dnn,mt);/输出各排序移动次数 void bubble_sort(int n,int A)/冒泡排序 int mt=0;/移动次数mt=movetime int ct=0;/比较次数ct=cmdtime int i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;in-1;i+) for(j=0;jn-1-i;j+,ct+) if(aj+1aj)/前后比较 temp=aj, aj=aj+1, aj+1=temp, mt+=3;/关键字交换计为3次移动 printf(冒泡排序); output(n,a,ct,mt); void selection_sort(int n,int A)/选择排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,temp,k; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;in-1;i+) k=i; for(j=i+1;jaj) k=j; temp=ai, ai=ak, ak=temp, mt+=3;/关键字交换计为3次移动 printf(选择排序); output(n,a,ct,mt); void quick(int a,int low,int up)/快速排序递归算法 int i,j,temp; if(lowup) i=low; j=up; temp=alow, qmt+; while(i!=j) qct+; while(itemp) j-, qct+; if(ij) ai+=aj, qct+; qmt+; while(ij&ai=temp) i+, qct+; if(ij) aj-=ai, qct+, qmt+; ai=temp, qmt+; quick(a,low,j-1); quick(a,i+1,up); void quick_sort(int n,int A)/快速排序(通过调用快速排序递归算法完成) int i; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) quick(a,0,n-1);/调用快速排序递归算法 printf(快速排序); output(n,a,qct,qmt); 710内部排序演示C+void insertion_sort(int n,int A)/插入排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=1;i=0&tempaj;j-,ct+) aj+1=aj, mt+; aj+1=temp, mt+; printf(插入排序); output(n,a,ct,mt); void shell_sort(int n,int A)/希尔排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,k,h,y; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;it;i+) h=di; for(j=h;j=0&yak;k-=h) ak+h=a k; ak+h=y; printf(希尔排序); output(n,a,ct,mt); void main() int n; int i; int AN; printf(*内部排序*n); printf(请输入数组大小(小于100)：); scanf(%d,&n);/输入所需排序数组大小 for(i=0;in;i+) printf(请输入数组a%d：,i); scanf(%d,&Ai);/依次输入数组A0An bubble_sort(n,A);/冒泡排序 insertion_sort(n,A);/插入排序 selection_sort(n,A);/选择排序 quick_sort(n,A);/快速排序 shell_sort(n,A);/希尔排序 【使用说明】例如：*内部排序*请输入数组大小(小于100)：8请输入数组a0：12请输入数组a1：23请输入数组a2：18请输入数组a3：36请输入数组a4：27请输入数组a5：9请输入数组a6：21请输入数组a7：14冒泡排序排序结果：9 12 14 18 21 23 27 36比较次数：28移动次数：45插入排序排序结果：9 12 14 18 21 23 27 36比较次数：15移动次数：29选择排序排序结果：9 12 14 18 21 23 27 36比较次数：28移动次数：21快速排序排序结果：9 12 14 18 21 23 27 36比较次数：22移动次数：16希尔排序排序结果：9 12 14 18 21 23 27 36比较次数：16移动次数：32【调试分析说明】这是我们学过几种内部排序方法的综合，并在之前的基础上增加计算排序方法的比较次数和移动次数，在调试过程中，相当于各种方法独立的排序，所以没有遇到太大的问题，值得注意的是对比较次数和移动次数的计算，出现过一些小麻烦，需要细心的调试。【算法的改进设想】这是我们学过几种内部排序方法的综合，所以在编写过程中是各自为战，没有一个整体性，另外，程序统计出比较次数和移动次数，但还没有比较明确的比较结果，这一点需要我们以后继续改进。【总结】在6个题目中，这个是我相对有把握的一道题目，可是在编写，调试的过程中虽然没有太大的问题，可是也没有我想象中的简单。排序方法的比较是我们之前学过几种排序方法的整合，给我最大的感受是把这些算法整合起来需要明确的思想和思路，需要整个程序的步调一致。推及到所有程序，都要我们在编程过程中注意程序的一致性。内部排序演示C+#include #define N 100/定义数组最大为100const int t=3;/定义希尔排序次数int dt=4,3,1;/定义希尔排序比较量int qmt;/快速排序的移动次数int qct;/快速排序的比较次数 void output(int n,int a,int ct,int mt)/内部排序中调用的输出函数 int i; printf(n排序结果:); for( i=0;in;i+) printf(%d ,ai);/输出各排序完成的数组 printf(n比较次数:%dn,ct);/输出各排序比较次数 printf(移动次数:%dnn,mt);/输出各排序移动次数 void bubble_sort(int n,int A)/冒泡排序 int mt=0;/移动次数mt=movetime int ct=0;/比较次数ct=cmdtime int i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;in-1;i+) for(j=0;jn-1-i;j+,ct+) if(aj+1aj)/前后比较 temp=aj, aj=aj+1, aj+1=temp, mt+=3;/关键字交换计为3次移动 printf(冒泡排序); output(n,a,ct,mt); void selection_sort(int n,int A)/选择排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,temp,k; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;in-1;i+) k=i; for(j=i+1;jaj) k=j; temp=ai, ai=ak, ak=temp, mt+=3;/关键字交换计为3次移动 printf(选择排序); output(n,a,ct,mt); void quick(int a,int low,int up)/快速排序递归算法 int i,j,temp; if(lowup) i=low; j=up; temp=alow, qmt+; while(i!=j) qct+; while(itemp) j-, qct+; if(ij) ai+=aj, qct+; qmt+; while(ij&ai=temp) i+, qct+; if(ij) aj-=ai, qct+, qmt+; ai=temp, qmt+; quick(a,low,j-1); quick(a,i+1,up); void quick_sort(int n,int A)/快速排序(通过调用快速排序递归算法完成) int i; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) quick(a,0,n-1);/调用快速排序递归算法 printf(快速排序); output(n,a,qct,qmt); void insertion_sort(int n,int A)/插入排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=1;i=0&tempaj;j-,ct+) aj+1=aj, mt+; aj+1=temp, mt+; printf(插入排序); output(n,a,ct,mt); void shell_sort(int n,int A)/希尔排序 int mt=0;/移动次数movetime int ct=0;/比较次数cmdtime int i,j,k,h,y; int aN; for(i=0;in;i+) ai=Ai;/使数组a与数组A完全相同,对数组a进行操作(不改动A,可以使A被其他函数调用) for(i=0;it;i+) h=di; for(j=h;j=0&yak;k-=h) ak+h=ak; ak+h=y; printf(希尔排序); output(n,a,ct,mt); void main() int n; int i; int AN; printf(t*n); p