文档介绍：北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
数据结构实验报告
1．实验要求
实验目的
经过选择下面两个题目之第三次实验排序总结
{intexchange=Max;intbound,j;while(exchange)
{bound=exchange;exchange=0;for(j=1;j<bound;j++)
{comparetimes[2]++;
if(parray[j]>parray[j+1])
{parray[0]=parray[j];parray[j]=parray[j+1];parray[j+1]=parray[0];exchange=j;
movetimes[2]+=3;}}}
return0;}
示意图：
r1,r2,r3,,ri-1,ri,ri+1,,rn
反序则互换有序区
<4>迅速排序：首先选择一个基准，将记录切割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序达成。
intSort::QuickSort(longintparray[])
{QuickSortRecursion(parray,1,Max);return0;}
intSort::QuickSortRecursion(longintparray[],intfirst=1,intend=Max)
{if(first<end)
{intpivot=QuickSortPatition(parray,first,end);
QuickSortRecursion(parray,first,pivot-1);//左侧子序列排序
QuickSortRecursion(parray,pivot+1,end);//右侧子序列排序}
return0;}
intSort::QuickSortPatition(longintr[],intfirst,intend)
{inti=first;intj=end;inttemp;
while(i<j)
{while(i<j&&r[i]<=r[j]){j--;
comparetimes[3]++;}//右侧扫描
if(i<j)
{temp=r[i];//将较小记录互换到前面
r[i]=r[j];
r[j]=temp;
i++;
movetimes[3]+=3;}
北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
第3页
北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
北邮数据结构实验第三次实验排序总结
while(i<j&&r[i]<=r[j])
{
i++;
comparetimes[3]++;
}//左侧扫描
if(i<j)
{
temp=r[j];
r[j]=r[i];
r[i]=temp;//将较大记录互换到后边
j--;
movetimes[3]+=3;}}
returni;//i为轴值记录的最终地点
示意图：
r1,r2,r3,,ri-1,ri,ri+1,,rn
r<ri轴值r>ri
<5>选择排序：从待排序的记录序列中选择重点码最小（或最大）的记录并将它与序列中
的第一个记录互换地点；然后从不包括第一个地点上的记录序列中选择重点码最小（或最大）
的记录并将它与序列中的第二个记录互换地点；如此重复，直到序列中只剩下一个记录为止。
intSort::SelectSort(longintparray[])
{
inti,j,index,temp;
for(i=1;i<Max;i++)//对n个记录进行n-1趟简单项选择择排序
{
index=i;
for(j=i+1;j<=Max;j++)
{
comparetimes[4]++;//在无序区中选用最小记录
if(parray[j]<parray[index])
index=j;
}
if(index!=i)
{
temp=parray[i];
parray[i]=parray[index];
parra