排序算法比较.docx

1、排序算法比较数据结构的课程设计报告题目：排序算法比较 班级： 1612401 学号： 161240113 姓名： 张修鸣 指导老师： 孙涵 完成日期： 2014.1.3 目 录一.需求分析.二.程序主要功能.三.程序运行平台.四.程序类说明.五. 模块分析.六. 存在的不足与对策.七体验感悟八. 程序源代码.需求分析利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（即比

2、较次数）。程序主要功能（1） 原始数据存在文件中，每个整数一行，方便读入。（2） 屏幕显示每种排序所花的比较次数。程序运行平台 该程序是用VC+6.0制做的，使用Microsoft Visual C+ 6.0运行该程序，具体操作是：打开Microsoft Visual C+ 6.0，菜单栏里点文件打开工作区找到“图书管理系统.dsw”这个文件打开，或者在资源管理器中双击该文件，此时，VC+6.0会自动打开，并载入该系统相关资源，点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。trl计分析能_程序类说明函数分析： int BubbleSort(int a)/冒泡排序 int Selec

3、tionSort(int a)/选择排序 int insertsort(int a) /直接插入排序int BInsertSort(int a)/折半插入排序int Partitoin(int a,int low,int high)/快速排序int radixsort(int data,int n) /基数排序void heapsort( int *heap, int low, int high ) /堆排序模块分析当随机生成20000个数时程序运行分析随机生成数排序后存在的不足与对策由于自身能力有限，所以没有设计的堆排序和快排序差距较大。在设计过程中由于设计者的编程功底欠缺，因此学习过程较为

4、艰辛，需要解决的问题也比较多。在以后的学习中，应该循序渐进，不可急于求成，先打好基础，这样才能更好地发展。体验感悟在编写程序的过程中，深切的体会到自身能力还有待提高，通过大规模的查询网上资料与相关书籍我学习到了很多以前不知道的编程方法与各种奇妙的函数语句时，提高了自己对程序设计本身的兴趣，更加乐意去学习这方面的新的东西，并在不断地自我挑战中收获着，或知识技能，或信心勇气。希望自己在今后的学习中可以更好的完善自我。程序源代码# include using namespace std;# include# include # include # define SIZE 20000void crea

5、tData() int i,m; fstream file; file.open(data.txt,ios:out|ios:trunc); if(file.fail() cout打开文件失败!n; exit(0); srand(time(0); for (i = 0; i SIZE; i+) m=rand(); filemn; file.close();int BubbleSort(int a)/冒泡排序 int i, j, t,count=0; for (i = 0;iSIZE-1;i+) for (j = 0;jaj + 1) t = aj; aj = aj + 1; aj + 1 = t

6、; count+; return count;int SelectionSort(int a)/选择排序 int i,j,t,minIndex,count=0; for(i=0;iSIZE-1;i+) minIndex=i; for(j=i+1;jSIZE;j+) if(ajaminIndex) minIndex=j; if(minIndex!=i) t=aminIndex; aminIndex=ai; ai=t; count+; return count;int insertsort(int a) /直接插入排序 int count=0; for(int i=1; i=0 & tempaj

7、; -j) aj+1 = aj; count+; aj+1 = temp; return count; int BInsertSort(int a)/折半插入排序 int i,j,high,low,m,count=0; for (i=2; i=SIZE; +i) a0 = ai; low = 1; high = i-1; while (low=high) m = (low+high)/2; if (a0=high+1; -j) aj+1 = aj; ahigh+1 = a0; return count; int quicksort=0;int Partitoin(int a,int low,i

8、nt high)/快速排序 a0=alow; int pivotkey=alow; while(lowhigh) while(low=pivotkey)-high; alow=ahigh; while(lowhigh&alow=ahigh)+low; ahigh=alow; quicksort+; alow=a0; return low;void QSort(int a,int low,int high) int prvotloc; if(lowhigh) prvotloc=Partitoin(a,low,high); QSort(a,low,prvotloc-1); QSort(a,prvo

9、tloc+1,high); int maxbit(int data,int n) /求数据的最大位数 int i,p,max=0; int *temp; temp=new intn; for(i=0;in;i+)tempi=datai; for(i=0;i0) p+;tempi=tempi/10; if(pmax)max=p; deletetemp; return max;int radixsort(int data,int n) /基数排序 int *temp,count1=0; temp=new intn; int i,j,k; int count10; int radix=1; for(

10、i=radix;i=maxbit(data,n);i+) for(j=0;j10;j+)countj=0; for(j=0;jn;j+) k=(dataj/radix)%10; countk+; for(j=1;j=0;j-) k=(dataj/radix)%10; countk-; tempcountk=dataj; count1+; for(j=0;jn;j+) dataj=tempj; radix=radix*10; deletetemp; return count1;int heapsort=0;void heapAdjust( int *heap, int low, int high

11、 ) /堆排序 int i,temp = heaplow; for( i=low*2+1; i=high; i*=2) if( ihigh & heapi=heapi+1 ) i+; if( heapi =0; -i ) heapAdjust(heap,i,SIZE-1); for( i=SIZE-1 ; i0 ; -i ) temp=heap0; heap0=heapi; heapi=temp; heapAdjust(heap,0,i-1); int main() int i=0,aSIZE,bSIZE; fstream file,fp1,fp2,fp3,fp4,fp5,fp6,fp7; f

12、ile.open(data.txt,ios:in); fp1.open(a1.txt,ios:trunc|ios:out); fp2.open(a2.txt,ios:trunc|ios:out); fp3.open(a3.txt,ios:trunc|ios:out); fp4.open(a4.txt,ios:trunc|ios:out); fp5.open(a5.txt,ios:trunc|ios:out); fp6.open(a6.txt,ios:trunc|ios:out); fp7.open(a7.txt,ios:trunc|ios:out); if(file.fail()|fp1.fa

13、il()|fp2.fail()|fp3.fail()|fp4.fail()|fp5.fail()|fp6.fail()|fp7.fail() coutai; bi=ai; i+; cout直接插入排序的比较次数为: insertsort(a)endl; for (i = 0; i SIZE; i+) fp1 ain; for(i=0;iSIZE;i+) ai=bi; cout冒泡排序的比较次数为: BubbleSort(a)endl; for (i = 0; i SIZE; i+) fp2 ain; for(i=0;iSIZE;i+) ai=bi; cout选择排序的比较次数为: Select

14、ionSort(a)endl; for (i = 0; i SIZE; i+) fp3 ain; for(i=0;iSIZE;i+) ai=bi; heapSort(a); cout堆排序的比较次数为: heapsortendl; for (i = 0; i SIZE; i+) fp4 ain; int cSIZE+1; for(i=0;iSIZE;i+) ai=bi; cout折半插入排序的比较次数为: BInsertSort(a)endl; for (i = 1; i SIZE+1; i+) fp5 ain; for(i=0;iSIZE;i+) ci+1=bi; QSort(c,1,SIZE); cout快速排序的比较次数为: quicksortendl; for (i = 1; i SIZE+1; i+) fp6 cin; for(i=0;iSIZE;i+) ci+1=bi; cout基数排序的比较次数为: radixsort(c,SIZE)endl; for (i = 0; i SIZE; i+) fp7 cin; file.close();fp1.close();fp2.close();fp3.close();fp4.close();fp5.close();fp6.close();fp7.close(); return 0;