2010级数据结构实验报告实验名称：排序姓名：袁彬班级： 2009211120班内序号： 09学号： 09210552日期： 2010 年12 月19 日1．实验要求试验目的：通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。
试验内容：题目一：使用简单数组实现下面各种排序算法，并进行比较。
排序算法如下：①插入排序；②希尔排序③冒泡排序；④快速排序；⑤简单选择排序；⑥堆排序⑦归并排序⑧基数排序⑨其他。
具体要求如下：①测试数据分为三类：正序，逆序，随机数据。
②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。
③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。
④对②和③的结果进行分析，验证上述各种算法的时间复杂度。
⑤编写main()函数测试各种排序算法的正确性。
题目二：使用链表实现下面各种排序算法，并进行比较。
排序算法如下：①插入排序；②冒泡排序；③快速排序；④简单选择排序；⑤其他。
具体要求如下：①测试数据分为三类：正序，逆序，随机数据。
②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。
③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作）④对②和③的结果进行分析，验证上述各种算法的时间复杂度。
⑤编写main()函数测试各种排序算法的正确性。
2. 程序分析2.1 存储结构程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。
程序的储存结构采用数组。
数组的第一个位置不存储数据。
数据从第二个位置开始。
数组中的相对位置为数组的下标。
2.2 关键算法分析㈠、关键算法：1、插入排序函数：Insert s ort(int n)①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++)②、如果后面的比前面的小，则进行前移：if(number[i]<number[i-1])③、设置哨兵：number[0]=number[i];④、如果后面的比前面的小，前面的进行后移：for(j=i-1;number[0]<number[j];j--)⑤、前面的进行后移：number[j+1]=number[j];⑥、将比较的数据放置到正确位置：number[j+1]=number[0];2、希尔排序函数：Shell i nsert(int n)①、以长度的一半为间隔进行循环：for(int d=n/2;d>=1;d=d/2)②、在自己的间隔中进行简单插入排序，进行循环：for(int i=d+1;i<=n;i++)③、如果后面的数据比前面的小，进行前移：if(number[i]<number[i-d])④、设置哨兵：number[0]=number[i];⑤、在自己的间隔中进行简单插入排序：for(j=i-d;number[0]<number[j]&&j>0;j=j-d)⑥、大的数据后移：number[j+d]=number[j];⑦、哨兵归位：number[j+d]=number[0];3、冒泡排序函数：Bubble s ort(int n)①、设置有序无序的边界点：int pos=n;②、当边界点不为空进行循环：while(pos!=0)③、边界点传递给bound：int bound=pos;④、从开始到边界点进行循环：for(int i=1;i<bound;i++)⑤、如果前面的数据比后面的大，进行交换：if(number[i]>number[i+1])⑥、交换：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0];⑦、从小设置边界点：pos=i;4、一趟快速排序函数：partion(int first,int end)①、传递设置整个数据的起点和终点：int i=first;int j=end;②、设置中轴：number[0]=number[i];③、当end大于first进行循环：while(i<j)④、当后面的数据大于中轴，后面的游标前移：while((i<j)&&(number[j]>=number[0])) j--;⑤、中轴和比它大的数据进行交换：number[i]=number[j];⑥、当前面的数据小于中轴，前面的游标后移：while((i<j)&&(number[i]<=number[0]))i++;⑦、中轴和比它小的数据进行交换：number[j]=number[i];⑧、将中轴进行归位：number[i]=number[0];5、递归快速排序函数：Qsort(int i,int j)①、如果数组不为空，进行排序：if(i<j)②、一趟冒泡排序：int pivotloc=partion(i,j);③、递归将左右半面进行排序：Qsort(i,pivotloc-1);Qsort(pivotloc+1,j);6、简单选择排序函数：Select s ort(int n)①、从数组开始到结尾进行遍历：for(int i=1;i<n;i++)②、设置最小数据标记：int index=i;③、在无序区进行循环：for(int j=i+1;j<=n;j++)④、当出现比标记还小的数据，就进行交换：if(number[j]<number[index])index=j;⑤、如果最小的不是末尾的数，就进行交换：if(index!=i)⑥、进行交换：number[0]=number[i];number[i]=number[index];number[index]=number[0];7、一趟堆排序函数：sift(int k,int m)①、设置根节点和孩子的位置：int i=k,j=2*k;②、从左右孩子中选择出最小的孩子：if(j<m&&number[j]>number[j+1])j++;③、判断根节点是不是最小的，不是就进行交换：if(number[i]<number[j])break;④、进行交换：number[0]=number[i];number[i]=number[j];number[j]=number[0];⑤、将根节点和孩子位置后移，继续排序：i=j;j=2*i;8、递归堆排序函数：Heap s ort(int n)①、从最大非叶子节点，进行一趟堆排序：for(i=n/2;i>=1;i--)②、进行数组长度值的循环：for(i=1;i<n;i++)③、将根节点和尾节点进行交换：number[0]=number[1];number[1]=number[n-i+1];number[n-i+1]=number[0];④、在进行一趟堆排序：sift(1,n-i);9、一趟归并排序函数：Merge(int *r, int *r1, int s, int m, int t)①、传递设置两个数组的起点和终点：int i=s;int j=m+1;int k=s;②、当任意一个数组没有达到终点时，进行循环：while(i<=m&&j<=t)③、进行循环，将较小的值传给r1数组：if(r[i]<r[j])④、将较小的值传给r1数组：r1[k++]=r[i++];else r1[k++]=r[j++];⑤、当一个数字已经比较完，做循环将其续借到r1数组中：if(i<=m)while(i<=m)r1[k++]=r[i++];⑤、当另一个数字已经比较完，做循环将其续借到r1数组中：if(j<=t)while(j<=t)r1[k++]=r[j++];10、递归归并排序函数：MergeSort(int *r, int *r1, int s, int t)①、创建新数字指针存储排序序列：int *r2=new int[t];②、当序列中只有一个数据时，令其相等：if(s==t)r1[s]=r[s];③、否则，进行递归：else④、将原数组折半：int m=(s+t)/2;⑤、将前半数组进行递归调用：MergeSort(r,r2,s,m);⑥、将后半数组进行递归调用：MergeSort(r,r2,m+1,t);⑦、将数组进行递归调用：Merge(r2,r1,s,m,t);㈡、关键算法的时间、空间复杂度①、直接插入排序函数：时间复杂度O（n2）②、希尔排序函数：时间复杂度O(n㏒2 n)③、起泡排序：时间复杂度O（n2）④、快速排序：时间复杂度O(n㏒2 n)⑤、简单选择排序：时间复杂度O（n2）⑥、堆排序：时间复杂度O(n㏒2 n)⑦、归并排序：时间复杂度O(n㏒2 n)3. 程序运行结果测试主函数流程：程序流程图如下：4. 总结（1）、出现的问题及调试的方法这次试验总的来说是比较简单的，因为这七种排序算法的代码书上都有，在理解的基础上参考书上的代码输入基本上不会有太大的问题，但问题还是有的。
例如：一组待排序的整数存在一个数组中，当采用一种排序算法对这个数组进行排序后，数组就被修改了，变为有序的序列，这是一个问题，于是我动态申请了七个数组，每次排序对不同的数组进行，这个问题就解决了（2）、心得体会这次试验是我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。
在程序编译和链接时还报了一些错，最后我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。
在程序编译和链接时还报了一些错，最后通过一步一步的测试，也很快解决了问题。
通过这次程序我感觉我对C++调试有个很深的理解，对程序的调试有了很多心得，也对我的程序调试和编写有了进一步的提高。
同时对C++编程进一步熟悉，同时对数据结构有了一个整体的认识，对各种排序中函数成员实现的原理、代码进一步了解。
同时对各种排序的优缺点有了进一步的认识和了解。
在这个程序中，我觉得下一步程序可以进一步对时间复杂度进行优化，通过将程序的冗长的代码删除，优化算法等，让程序得到结果所需要的时间更短、更快，删除一些代码，让程序的空间复杂度和时间复杂度都减小。
（3）、下一步的改进程序中代码有一部分不是太简洁，例如七个数组、统计比较了移动次数这些代码显得比较乱。