北邮 数据结构 实验四数组排序文档格式.docx
《北邮 数据结构 实验四数组排序文档格式.docx》由会员分享，可在线阅读，更多相关《北邮 数据结构 实验四数组排序文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
r[i-1]）//查找插入位置
{
r[0]=r[i];
//设置哨兵
count2++;
intj;
for（j=i-1;
count1++,r[0]<
r[j];
j--）//寻找插入位置
{
r[j+1]=r[j];
//元素后移
count2++;
}
r[j+1]=r[0];
//插入记录
elsecount1++;
//此时虽然没有移动，但是已经进行了一次比较
}
for（intk=1;
k<
n;
k++）//将排序结果输出
cout<
<
r[k]<
"
"
;
cout<
endl;
比较次数为"
count1<
移动次数为"
count2<
}
直接插入排序的基本思想便是每将一个待排序的元素按其关键码的大小插入到一个已经排序好的有序序列中，直到全部元素都排好。
而我认为直接插入排序的程序中很关键的一点便是加入了监视哨兵，这时的程序的执行中不仅减少了空间的使用也节省了程序执行的时间。
2、希尔排序ShellSort（）：
voidShellSort（intr[],intn）//希尔排序
{
inti,d,j;
for（d=n/2;
d>
=1;
d=d/2）//以增量为d进行直接插入排序
{
for（i=d+1;
i++）//一趟希尔排序
{
r[0]=r[i];
//暂存被插入记录
for（j=i-d;
j>
0&
&
r[0]<
j=j-d）//每隔d个记录进行一次比较和移动
r[j+d]=r[j];
//记录后移d个位置
r[j+d]=r[0];
count1++;
count2=count2+d;
//每次都移动d个位置
count1++;
for（i=1;
i<
i++）//输出希尔排序结果
r[i]<
希尔排序而基本思想便是将带排序的元素及分成多个子集，分别对这些子集进行直接直接插入排序，带到真个程序基本有序时在对元素进行一次直接插入排序。
而为了使集合基本有序而不是局部有序，不能简单地逐段分割，而是将相距某个增量的元素组成一个子序列，这个增量逐步缩小，最后等于1，这样最终的结果就是整个序列有序。
3、起泡排序BubbleSort（）：
voidBubbleSort（intr[],intn）//起泡排序
inttemp,pos,bound;
pos=n-1;
//第一趟起泡排序的范围是r[1]到r[n]
while（pos!
=0）//仅当上一趟排序有记录交换才进行本趟排序
bound=pos;
//本次无序元素的范围
pos=0;
//控制外循环结束
for（intj=1;
j<
bound;
j++）//一趟起泡排序
//接下来有一次比较
if（r[j]>
r[j+1]）//相邻元素比较
{
temp=r[j];
//交换r[j]和r[j+1]
r[j]=r[j+1];
r[j+1]=temp;
pos=j;
//记录每一次发生记录交换的位置，当j=0时说明一次比较也没有了，即已经全部有序了
count2=count2+3;
//一个交换语句为一次移动，共移动了次
}
for（inti=1;
i++）//输出起泡排序结果
起泡排序的基本思想是两两比较相邻的元素，如果反序则交换位置，直到没有反序的元素为止。
由于基本的起泡排序算法每次只能添加一个元素到有序区，所以存在无序区的有序元素也需要比较的问题，为了去掉这种不必要的开销，可以将最后一次比较的位置pos作为下一趟无序区的末尾。
4、快速排序：
intPartition（intr[],intfirst,intend,int&
count1,int&
count2）//快速排序一次划分
inti=first;
//初始化
intj=end;
inttemp;
while（i<
j）
while（i<
j&
r[i]<
=r[j]）
j--;
//右侧扫描
if（i<
{
temp=r[i];
r[i]=r[j];
//将较小记录交换到前面
r[j]=temp;
i++;
count2=count2+3;
//左侧扫描
if（i<
temp=r[i];
r[i]=r[j];
r[j]=temp;
//将较大记录交换到后面
j--;
count1++;
returni;
//i为轴值记录的最终位置
voidQuickSort（intr[],intfirst,intend,int&
count2）//快速排序
if（first<
end）
{//递归结束,继续执行下边的操作
intpivot=Partition（r,first,end,count1,count2）;
//一次划分
QuickSort（r,first,pivot-1,count1,count2）;
//递归地对左侧子序列进行快速排序
QuickSort（r,pivot+1,end,count1,count2）;
//递归地对右侧子序列进行快速排序
快速排序的基本思想便是在分区中选一个元素作为轴值，将待排序元素划分为两个分区，使得左侧关键码均小于或等于轴值，右侧的关键码均大于或等于轴值，然后对着两个分区重复上述排序过程，直到整个序列有序。
5、简单选择排序SelectSort（）：
voidSelectSort（intr[],intn）//简单选择排序
inti;
intj;
intindex;
for（i=1;
i++）//对n个记录进行n-1趟简单选择排序
index=i;
//假设index是最小的
for（j=i+1;
j++）//在无序区中选取最小记录
if（r[j]<
r[index]）//如果该元素比现在第i个位置的元素小
index=j;
//赋值给index
//比较次数加一
//count1++;
//在判断不满足循环条件j<
n时，比较了一次
if（index!
=i）
//将无序区的最小记录与第i个位置上的记录交换
r[i]=r[index];
r[index]=temp;
//移动次数加
i++）
简单选择排序的基本思想是在每一趟的排序区中选出最小的元素换到前边，重复不断的执行，直到元素全部排序完为止。
6、堆排序：
voidSift（intr[],intk,intm,int&
count2）//筛选法调整堆,s，t分别为比较和移动次数,m为编号最大的叶子结点的编号
inti=k;
intj=2*i+1;
//置i为要筛的结点，j为i的左孩子
while（j<
=m）//筛选还没有进行到叶子
if（j<
m&
r[j]<
r[j+1]）
j++;
//比较i的左右孩子，j为较大者
count1=count1+2;
//该语句之前和之后分别有一次比较
if（r[i]>
r[j]）
break;
//根结点已经大于左右孩子中的较大者则结束循环
else
r[i]=r[j];
r[j]=temp;
//将根结点与结点j交换
i=j;
j=2*i+1;
//下一个被筛结点位于原来结点j的位置
voidHeapSort（intr[],intn）//堆排序
//计数器，计比较和移动次数
for（i=n/2;
i>
=0;
i--）//初始建堆，从下向上（从最后一个分支结点开始）的过程（整体）
Sift（r,i,n,count1,count2）;
for（i=n-1;
i>
0;
i--）//重复执行移走堆顶及重建堆的操作
temp=r[i];
//将堆顶元素与将堆顶记录和当前未经排序子序列r[1..i]中最后一个记录相互交换
r[i]=r[0];
r[0]=temp;
//完成一趟排序，输出记录的次序状态
Sift（r,0,i-1,count1,count2）;
//重建堆
堆排序是在简单选择排序的基础上进行了改进，即利用了前一趟比较后的结果，减少比较次数，从而提高了整个排序的效率。
而此次的对用的是大根堆。
7、归并排序：
voidMerge（intr[],intr1[],ints,intm,intt）//一次归并
inti=s;
//i指向r[s-m]
intj=m+1;
//j指向r[m+1-t]
intk=s;
//k指向r1
=m&
j<
=t）
if（r[i]<
=r[j]）
r1[k++]=r[i++];
//取r[i]和r[j]中较小者放入r1[k],并且自加
r1[k++]=r[j++];
if（i<
=m）
=m）//若第一个子序列r[s-m]没处理完，则进行收尾处理
while（j<
=t）//若第二个子序列r[m+1-t]没处理完，则进行收尾处理
r1[k++]=r[j++];
voidMergePass（intr[],intr1[],intn,inth）//一趟归并
inti=0;
intk;
=n-2*h）//待归并记录至少有两个长度为h的子序列
Merge（r,r1,i,i+h-1,i+2*h-1）;
i+=2*h;
//跳到下一个子序列进行比较排序
n-h）
Merge（r,r1,i,i+h-1,n）;
//待归并序列中有一个长度小于h
elsefor（k=i;
k<
=n;
k++）//待归并序列中只剩一个子序列
r1[k]=r[k];
voidMergeSort（intr[],intr1[],intn）//归并排序
inth=1;
while（h<
n）
MergePass（r,r1,n-1,h）;
//归并
h=2*h;
MergePass（r1,r,n-1,h）;
此处的归并排序违规并排序中最简单的二路归并排序，即先将n个元素的序列分为n个子序列，再按二倍的关系一一合成一个新的完整的序列。
将两个有序序列合成一个完整序列的方法是逐一对两个序列中的元素进行比较，并把较小者放入缓冲区，然后取出较小者所在的序列的下一个元素进行比较，往复执行，知道其中一个序列的元素全部放入缓冲区，再把另一个序列中的剩下的元素放在缓冲区的尾部。
8、主函数：
voidNewarray（inta[],intb[],intc[]）//产生顺序、逆序及随机数组
新随机数组：
c[0]=0;
a[0]=0;
b[0]=0;
for（ints=1;
s<
11;
s++）
a[s]=s;
b[s]=20-s;
c[s]=rand（）%50+1;
c[s]<
voidmain（）
srand（time（NULL））;
constintnum=11;
//赋值，最大的数组的容量
inta[num];
intb[num];
intc[num];
intc1[num];
Newarray（a,b,c）;
顺序数组：
num;
j++）
a[j]<
逆序数组：
b[j]<
插入排序结果为：
\n"
InsertSort（a,num）;
InsertSort（b,num）;
InsertSort（c,num）;
希尔排序结果为：
ShellSort（a,num）;
ShellSort（b,num）;
ShellSort（c,num）;
起泡排序结果为：
BubbleSort（a,num）;
BubbleSort（b,num）;
BubbleSort（c,num）;
快速排序结果为：
QuickSort（a,0,num-2,count1,count2）;
a[i]<
count1=0,count2=0;
QuickSort（b,0,num-2,count1,count2）;
b[i]<
QuickSort（c,0,num-1,count1,count2）;
c[i]<
cout<
简单选择排序结果为：
<
SelectSort（a,num）;
SelectSort（b,num）;
SelectSort（c,num）;
堆排序结果为：
HeapSort（a,num）;
HeapSort（b,num）;
HeapSort（c,num）;
归并排序结果为：
MergeSort（a,c1,num）;
MergeSort（b,c1,num）;
MergeSort（c,c1,num）;
2、代码详细分析：
比如单链表的删除，需要将5句关键代码写清楚，并画出示意图
1、直接插入排序：
[1]当插入元素不超过数组长度时进行下列操作
[1]设置哨兵并查找插入位置
[3]插入记录
[2]将排序结果输出
示意图：
2、快速排序：
[1]一次划分快速排序
[2]递归地对左侧子序列进行快速排序
[3]递归地对右侧子序列进行快速排序
3.简单选择排序
[1]初始化参数
[2]对n个记录进行n-1趟排序
[1]在未排序记录中选出最小的元素
[2]将该最小元素往前排到有序区中
[3]输出排序结果
4、冒泡排序BubbleSort（）：
[1]当i不超过数组元素个数时，进行下边的操作
[1]左右相邻两个元素进行比较大小，大的往后排，小的往前排
[2]挡序列全部有序时停止操作
[2]输出冒泡排序结果
5、堆排序：
[1]对二叉树的n个进行循环筛选操作建大顶堆
[2]将建成的大顶堆的根结点与未进行排序的数组记录的最后一个进行交换
[3]接着对序列剩下的n-1个元素继续重新开始建堆并在建好堆后重复[2]操作直到序列全部有序为止
[4]将冒泡排序的结果输出
6、归并排序：
[1]将元素分为n个子序列
[2]将n个子序列内部进行简单插入排序后再逐渐合并为n/2、n/4,。
。
个子序列，直到序列全部有序为止
[3]将归并排序结果输出
示意图;
3、计算关键算法的时间、空间复杂度
排序方法
平均情况
最好情况
最坏情况
辅助空间
直接插入排序
O（n2）
O（n）
O
（1）
希尔排序
O（nlog2n）~O（n2）
O（n1.3）
起泡排序
O（n）
快速排序
O（nlog2n）
O（log2n）~O（n）
简单选择排序
堆排序
O（nlog2n）
归并排序
2.3其他
1、可选，你认为还需要补充的任何说明都可以
3.程序运行结果
1、测试主函数流程：
流程图如图2所示
主函数main（）
初始化随机数组
堆排序：
HeapSort（）
其他的一些排序，如归并排序等
直接插入排序：
InsertSort（）
冒泡排序：
BubbleSort（）
希尔排序：
ShellSort（）
快速排序：
Qsort（）
2、测试条件：
比如问题规模n的数量级是多少？
插入、删除元素的位置如何选择？
n为10
3、测试结论
4.总结
[正文格式要求]见1实验要求中的格式要求
1、调试时出现的问题及解决的方法
2、心得体会
3、下一步的改进
1、生成数组函数及本程序中的代码有的采用了递归的形式，如果考虑用栈来模拟的话，效率会有提升，所以运行时间还和代码的实现有关，代码本身只是描述了算法思想，并没有再进行编写方面的优化，因而还不能完全反映出每个算法的根本性能。
2、可以试着去编写可以计算出时间的函数
3、程序中用来测试的数据量太小误差大，应考虑用大量的数据来验证移动和
升级会员 