北京邮电大学数据结构实验第三次实验排序Word格式文档下载.docx
《北京邮电大学数据结构实验第三次实验排序Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《北京邮电大学数据结构实验第三次实验排序Word格式文档下载.docx（17页珍藏版）》请在冰点文库上搜索。
A0
A1
A2
A3
A4
A5
A6
3.2关键算法分析
1.插入排序：
依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕
voidInsertsort（intr[],intn,int*compare,int*move）//插入排序
{
*compare=0;
*move=0;
inti;
intj;
for（i=1;
i<
n;
i++）//一共要排序n-1次
{intx=r[i];
for（j=i-1;
x<
r[j]&
&
j>
=0;
j--）
（*compare）++;
（*move）++;
r[j+1]=r[j];
}
if（j>
=0）
（*compare）++;
r[j+1]=x;
2.希尔排序：
先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序
voidShellInsert（intr[],intn,int*compare,int*move）//希尔排序
for（intd=n/2;
d>
=1;
d=d/2）//间距越来越小
for（inti=d;
=n-1;
i++）//从a[d]往后逐个元素确定是否需要前移{if（r[i]<
r[i-d]）//某元素比同组中的前一位小，则需要前移
for（j=i-d;
（j>
=0）&
（x<
r[j]）;
j=j-d）//完成所需的所有前移{（*compare）++;
r[j+d]=r[j];
if（j>
r[j+d]=x;
else（*compare）++;
3.冒泡排序：
两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止
voidBubblesort（intr[],intn,int*compare,int*move）//交换（冒泡）排序{*compare=0;
intx;
for（intj=0;
j<
n-1;
j++）//冒泡排序n-1次
for（inti=n-1;
i>
j;
i--）
if（r[i]<
r[i-1]）
（*move）+=3;
x=r[i];
r[i]=r[i-1];
r[i-1]=x;
}
}
4.快速排序：
首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成
intPartion（intr[],intfirst,intend,int*compare,int*move）//快速排序中的轴定位
{inti=first;
intj=end;
intzhou=r[i];
//默认第一个元素为轴
while（i<
j）
while（（i<
j）&
（r[j]>
=zhou））//查看右侧元素与轴的大小关系
j--;
if（i<
{（*compare）++;
r[i]=r[j];
//发现轴右侧的某数比轴值小，将其前置
}while（（i<
（r[i]<
=zhou））//查看左侧元素与轴的大小关系{（*compare）++;
i++;
r[j]=r[i];
//发现轴左侧的某数比轴值小，将其后置
}
r[i]=zhou;
//最后确定轴的位置returni;
voidQsort（intr[],inti,intj,int*compare,int*move）//快速排序
{if（i<
{intcentre=Partion（r,i,j,compare,move）;
Qsort（r,i,centre-1,compare,move）;
Qsort（r,centre+1,j,compare,move）;
5.选择排序：
从待排序的记录序列中选择关键码最小的记录并将它与序列中的第一个记录交换位置；
然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；
如此重复，直到序列中只剩下一个记录为止
voidSelectsort（intr[],intn,int*compare,int*move）//选择排序
{*compare=0;
for（inti=0;
i++）//排序n-1次
Intmin=i;
for（intj=i+1;
j++）//通过此层循环，找到真正的第i个最小值
{（*compare）++;
if（r[j]<
r[min]）
min=j;
//记录下当前找到的最小值的位置
if（min!
=i）
{
intMin;
Min=r[min];
r[min]=r[i];
r[i]=Min;
时间复杂度，空间复杂度
排序方法
平均情况
最好情况
最坏情况
辅助空间
直接插入排序
O（n²
）
O（n）
O
（1）
希尔排序
O（nlog2n）~O（n）
O（n的1.3次幂）
起泡排序
快速排序
O（nlog2n）
O（log2n）~O（n）
简单选择排序
原始代码：
#include<
iostream>
usingnamespacestd;
voidInsertSort（intr[],intn）
{
intnum1=0;
intnum2=0;
for（inti=2;
i++）
{
r[i-1]）
{
r[0]=r[i];
r[i]=r[i-1];
for（intj=i-1;
r[0]<
r[j];
j--,num1++）
{r[j+1]=r[j];
num2=num2+3;
}
num1++;
r[j+1]=r[0];
}
}
cout<
<
"
直接插入排序后的数组为：
;
for（intk=1;
k<
k++）
cout<
r[k]<
"
endl;
比较次数为：
num1<
移动次数为：
num2<
voidShellSort（intr[],intn）
for（intd=n/2;
d=d/2）
for（inti=d+1;
if（r[i]<
r[i-d]）
{
r[0]=r[i];
for（intj=i-d;
0&
j=j-d,num1++）
{r[j+d]=r[j];
num2=num2+3;
}
r[j+d]=r[0];
num1++;
希尔排序后的数组为：
voidBubbleSort（intr[],intn）
intpos=n;
while（pos!
=0）
intbound=pos;
pos=0;
for（inti=1;
bound-1;
if（r[i]>
r[i+1]）
r[i]=r[i+1];
r[i+1]=r[0];
pos=i+1;
num2+=3;
}num1++;
冒泡排序后的数组为：
intPartion（intr[],intfirst,intend,int&
num1,int&
num2）
inti=first;
intj=end;
intpivot=r[i];
while（i<
{
while（（i<
=pivot））
j--;
if（i!
=j）
=pivot）&
num1++）
i++;
r[j]=r[i];
if（i!
num2=num2+3;
r[i]=pivot;
returni;
voidQsort（intr[],inti,intj,int&
num2）
if（i<
intpivotloc=Partion（r,i,j,num1,num2）;
Qsort（r,i,pivotloc-1,num1,num2）;
Qsort（r,pivotloc+1,j,num1,num2）;
voidSelectSort（intr[],intn）
intnum1=0,num2=0;
for（inti=1;
i++）
intindex=i;
for（intj=i+1;
j++,num1++）
if（r[j]<
r[index]）
index=j;
if（index!
=i）
r[i]=r[index];
r[index]=r[0];
简单选择排序后的数组为：
voidRand（inta[],intr）
for（into=1;
o<
=10;
o++）
a[o]=rand（）;
voidmain（）
正反序排序结果为：
intr[10]={0,1,3,5,7,9,11,13,15,17};
InsertSort（r,10）;
intR[10]={0,17,15,13,11,9,7,5,3,1};
InsertSort（R,10）;
inta[10]={0,2,4,6,8,10,12,14,16,18};
BubbleSort（a,10）;
intA[10]={0,18,16,14,12,10,8,6,4,2};
BubbleSort（A,10）;
intb[10]={0,3,6,9,12,15,18,21,24,27};
ShellSort（b,10）;
intB[10]={0,27,24,21,18,15,12,9,6,3};
ShellSort（B,10）;
intc[10]={0,1,2,3,4,5,6,7,8,9};
Qsort（c,1,10,num1,num2）;
快速排序后的数组为：
=9;
c[k]<
intC[10]={0,9,8,7,6,5,4,3,2,1};
Qsort（C,1,10,num1,num2）;
for（intq=1;
q<
q++）
C[q]<
intd[10]={0,1,3,8,99,444,456,568,888,997};
SelectSort（d,10）;
intD[10]={0,997,888,568,456,444,99,8,3,1};
SelectSort（D,10）;
intn[10]={0,0,0,0,0,0,0,0,0,0};
随机数组排序结果：
Rand（n,10）;
InsertSort（n,10）;
BubbleSort（n,10）;
ShellSort（n,10）;
Qsort（n,1,10,num1,num2）;
for（intK=1;
K<
K++）
n[K]<
SelectSort（n,10）;
总结：
这次排序总体比较简单，所以调试程序所用时间不长。
但是对结构还是不够熟练，对比较次数和移动次数的计数还存在一定问题。
流程图
升级会员 