内排序实习总结.doc

内排序实习总结篇一：数据结构实习报告_排序数据结构课程设计实习报告题 目：学 号：姓 名：年 级：学 院：专 业：完成日期：授课教师：四个排序算法的比较 1210522 何厚华 大二 计算机与控制工程学院 计算机科学与技术 2014年5月25日 辛运帏目录1.题目. 22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序实现 . . . . . . . . . . . . . . . . . . . . . 23.1程序运行及编译环境. . . . . . . . . . . . . . . . 23.2程序描述 . . . . . . . . . . . . . . . . . 23.3实现功能 . . . . . . . . . . . . . . . . . . 33.3.1子功能模块 . . . . . . . . . . . . . . . . . 子功能模块1 . . . . . . . . . . . . . . 子功能模块2. . . . . . . . . . . . . . . 子功能模块3. . . . . . . . . . . . . . . 子功能模块4. . . . . . . . . . . . . . 子功能模块5. . . . . . . . . . . . . . . 子功能模块6. . . . . . . . . . . . . . .子功能模块7. . . . . . . . . . . . . . .9 3.3.2 数据结构. . . . . . . . . . . . . . . . . . . . 103.3.3算法及程序说明. . . . . . . . . . . . . . . . . . 103.4运行结果. . . . . . . . . . . . . . . . . . . 123.5尚未解决的问题 . . . . . . . . . . . . . . . . . . 151.题目四个排序算法的比较给定N个int类型（自定义N的上限M，例如M=100000，N的取值不能少于10000）的整数，分别使用插入排序、快速排序、希尔排序和堆排序方法进行升序排序。具体要求：1 四种排序方法均能得到正确的排序结果。2 分别统计四种排序中关键字比较的次数和记录交换的次数，并将统计结果显示出来。2.要求：初始数据使用随机数发生器产生，并使用程序自动检验排序结果的正确性。同时，需要编写一个检验随机性的小测试程序，分别统计各数段间数据的个数。数段的划分自定。例如可以按1000为一单位，分别统计（0，999）、（1000，1999）、（N-1000，N-1）之间的数据个数。如果N较大，也可以按10000为一单位。总之，只要能说明问题即可。在一个数段内，还可以再分析各子数段中数据的个数，例如选定（1000，1999）数段，然后以100为一单位，统计这10个子数段中的数据个数。3.程序实现3.1程序运行及编译环境程序是用Visual Studio 2010即VS10.0 编译的。可以在windows系列的操作系统上运行。3.2程序描述该程序主要用于实现了插入排序，希尔排序，快速排序和堆排序的算法，然后比较各种算法在系统产生的上万个随机数下排序的各种参数，这些参数主要有：比较次数，移动次数，交换次数，排序耗时。然后，验证了每一种排序结果的正确性，最后，统计了随机数组的分布情况，以判断系统产生的随机数是否均匀。其流程如下：A).产生上万个随机数，并处理成满足范围条件的随机数B).依次进行插入排序，希尔排序，快速排序，堆排序并且获得它们的主要参数C).验证排序结果的正确性D).统计随机数的区间分布E).完成3.3实现功能A.统计随机数的区间分布B.检验排序结果的正确性C.实现插入排序算法D.实现希尔排序算法E.实现快速排序算法F.实现建堆，整堆算法G.在建堆，整堆的基础上实现堆排序的算法3.3.1 子功能模块 子功能模块1/*函数原型：void RandomTest(int a,int n);函数参数：a表示测试的数组，n表示数组元素个数函数功能：随机性检测，把它们分到50个区间里面去*/void RandomTest(int a,int n)coutsetw(5)i*interval,setw(6)(i+1)*interval)setw(6)Countiendl; int interval=MAXIMUM/INTERVALCOUNT; int CountINTERVALCOUNT; for(int i=0;iINTERVALCOUNT;i+) Counti=0; for(int i=0;in;i+) Countai/interval+;/把这个数加入到对应的区间中去 cout统计结果如下：endl区间 个数endl; for(int i=0;iINTERVALCOUNT;i+)子功能模块2/* 函数原型：bool IsOrder(int a,int n,bool IsReverse=false)；函数参数：int a表示待判断的数组int n表示数组的前n项bool IsReverse=false，表示这个数组按照升序还是反序排列，默认为升序 函数功能：用于判断排序结果的正确性*/ bool IsOrder(int a,int n,bool IsReverse=false)/true,表降序,false,表升序switch (IsReverse) case true:for(int i=1;in-1;i+)if(aiai+1) cout排序有误！请检查排序算法！endl;/检测到有逆序排列的 /coutiaii+1ai+1endl; return false; cout恭喜你，排序算法成功！endl; return true; case false: return true; 子功能模块3/* 函数原型：void InsertSort(int a,int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT)；篇二：内排序算法总结内排序算法总结package com.SoerAlgorithm;import java.util.Arrays;public class SelectSort /* param args*/public static void main(String args) / TODO Auto-generated method stubDataWrap data=new DataWrap(21,),new DataWrap(49,),new DataWrap(30,*),new DataWrap(16,),new DataWrap(30,),new DataWrap(9,);int data2=1100,192,221,12,13;System.out.println(排序之前:+java.util.Arrays.toString(data2);radixSort(data2,10,4);System.out.println(n);System.out.println(排序之后:+java.util.Arrays.toString(data2);/* 直接选择排序*/public static void selectSort(DataWrap data)System.out.println(开始排序:);int len=data.length;DataWrap temp;for(int i=0;ilen-1;i+)for(int j=i+1;jlen;j+)if(pareTo(dataj)0)temp=datai;datai=dataj;dataj=temp;System.out.println(java.util.Arrays.toString(data);/* 直接排序的改进算法*/public static void selectSort2(DataWrap data)System.out.println(开始排序:);int len=data.length;DataWrap temp;for(int i=0;ilen-1;i+)int minindex=i;for(int j=i+1;jlen;j+)if(pareTo(dataj)0)if(pareTo(dataj)0) minindex=j;if(minindex!=i)temp=datai;datai=dataminindex;dataminindex=temp;System.out.println(java.util.Arrays.toString(data);/* 冒泡排序*/public static void bubbleSort(DataWrap data)System.out.println(开始排序:);int len=data.length;for(int i=0;ilen-1;i+)boolean flag=false;for(int j=0;jlen-i-1;j+)if(pareTo(dataj+1)0)/ DataWrap temp=dataj+1;/ dataj+1=dataj;/ dataj=temp;Swap(data,j+1,j);flag=true;System.out.println(java.util.Arrays.toString(data); if(!flag)break; /* * 交换元素 */ public static void Swap(DataWrap data,int i,int j) DataWrap temp=datai; datai=dataj; dataj=temp; /* * 快速排序 */ public static void QuickSort(DataWrap data) SubqucikSort(data,0,data.length-1); public static void SubqucikSort(DataWrap data,int start,int end) /需要排序 if(startend)/以第一个元素作为分界值DataWrap base=datastart;int i=start;/从i的左边开始搜索int j=end+1;/从j的右边开始搜索while(true) while(iend && data+pareTo(base)=0); while(jstart && pareTo(base)=0); if(ij) Swap(data,i,j); else break; Swap(data,start,j);/递归左子序列SubqucikSort(data,start,j-1);/递归右子序列SubqucikSort(data,j+1,end); elsethrow new RuntimeException(越界); /* * 插入排序 */ public static void InsertSort(DataWrap data)int arrayLength = data.length; for (int i = 1 ; i arrayLength ; i+ ) /当整体后移时，保证datai的值不会丢失DataWrap tmp = datai;/i索引处的值已经比前面所有值都大，表明已经有序，无需插入/（i-1索引之前的数据已经有序的，i-1索引处元素的值就是最大值）if (pareTo(datai - 1) 0) int j = i - 1; /整体后移一格 for ( ; j = 0 && pareTo(tmp) 0 ; j-) dataj + 1 = dataj; /最后将tmp的值插入合适位置 dataj + 1 = tmp;System.out.println(java.util.Arrays.toString(data); /* * 二分排序,也叫折半排序 */ public static void binSort(DataWrap data) System.out.println(开始排序：n); int arrayLength = data.length; for(int i=0;iarrayLength;i+)DataWrap temp=datai;int low=0;int high=i-1;while(low=high) int mid=(low+high)/2; if(pareTo(datamid)0) high=mid-1; else low=mid+(转 自 于:wWW.Hn1C.cOM 唯才教育 网:内排序实习总结)1; for(int j=i;jlow;j-) dataj=dataj-1;datalow=temp; System.out.println(java.util.Arrays.toString(data); /*/ public static void HeapSort(DataWrap data) System.out.println(开始排序:); int len=data.length; for(int i=0;ilen-1;i+)BuildMaxHeap(data,len-1-i);Swap(data,0,len-1-i);System.out.println(java.util.Arrays.toString(data); public static void BuildMaxHeap(DataWrap data,int lastIndex) for(int i=(lastIndex-1)/2;i=0;i-)/保存当前正在判断的节点int k=i;while(k*2+1=lastIndex) int biggerIndex=2*k+1; if(biggerIndexlastIndex) if(databiggerIpareTo(databiggerIndex+1)0)biggerIndex+; if(pareTo(databiggerIndex)0) /交换 Swap(data,k,biggerIndex); k=biggerIndex; else break; /* * Shell排序 * Shell排序是以h为增量的排序算法，直接插入排序算法可以看做是h=1的Shell排序 */ public static void shellSort(DataWrap data) System.out.println(开始排序:); int len=data.length; int h=1; while(hlen/3)h=3*h+1; while(h0)System.out.println(=h的为:+h+=);for(int i=h;ilen;i+)篇三：大学校内个人实习总结实习总结每个学校都有实习，实习是一个大学生必须经历的从大学校园生活向社会实践生活的一个的过渡。大学阶段就快结束，对我来说时间可以说是白驹过隙，流逝得不知不觉，蓦然回首，自己还是大一刚刚报道，无忧无虑，满目憧憬的新生。很难想象自己就快要大学毕业了，想到要走进社会了，心中难免有点惆怅，有点胆怯，但我想更多的是期待吧。谈到本次校内实习，学校为我们安排了这次为期两周的校内实习，目的是为了给我们走出学校进入社会的一个过渡的阶段，让我们将学校里所学的理论知识与实际操作相结合，为进入社会奠定更加结实的基础。在短短的为期两周的校内实习里，我感到收获颇丰，指导老师对我实验过程中存在的错误给予指出，给予了正确的指导，让我明白了认真做好每一个实验对待每一个细节的重要性，所有这些，对我以后的工作都提供了实践基础。我从客观上对自己所学的有关方面的知识有了更深刻的认识，使自己更加充分地了解了理论与实习或实践的紧密联系的重要性。