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[0]=number[i];
④、如果后面的比前面的小，前面的进行后移：for(j=i-1;number[0]⑤、前面的进行后移：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[0]=number[i];
⑤、在自己的间隔中进行简单插入排序：for(j=i-d;number[0]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⑤、如果前面的数据比后面的大，进行交换：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④、当后面的数据大于中轴，后面的游标前移：while((i=number[0])) j--;
⑤、中轴和比它大的数据进行交换：number[i]=number[j];
⑥、当前面的数据小于中轴，前面的游标后移：while((ii++;
⑦、中轴和比它小的数据进行交换：number[j]=number[i];
⑧、将中轴进行归位：number[i]=number[0];
5、递归快速排序函数：Qsort(int i,int j)
①、如果数组不为空，进行排序：if(i②、一趟冒泡排序：int pivotloc=partion(i,j);
③、递归将左右半面进行排序：Qsort(i,pivotloc-1);Qsort(pivotloc+1,j);
6、简单选择排序函数：Select s ort(int n)
①、从数组开始到结尾进行遍历：for(int i=1;i②、设置最小数据标记：int index=i;
③、在无序区进行循环：for(int j=i+1;j<=n;j++)
④、当出现比标记还小的数据，就进行交换：if(number[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(jnumber[j+1])j++;
③、判断根节点是不是最小的，不是就进行交换：if(number[i]④、进行交换：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③、将根节点和尾节点进行交换：
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]④、将较小的值传给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);
㈡、关键算法的时间、空间复杂度
