文档介绍：精选学****资料
- - - - - - - - -
数据结构试验报告
1．试验要求
〔1〕 试验目的
通过挑选下面两个题目之一,学****实现、对比各种排序算法,把握各种排序算法的优 劣,以及各种算法使用的情形；
hile〔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;}}}
return 0;}
示意图：
r1,r2,r3,
⋯ ,ri
- 1,ri,ri+1,
⋯ ,rn
反序就交换
有序区
<4>快速排序：第一挑选一个基准,将记录分割为两部分,左支小于或等于基准,右支就 大于基准,然后对两部分重复上述过程,直至整个序列排序完成；
int Sort::QuickSort〔long int parray[]〕
{QuickSortRecursion〔parray,1, Max〕;return 0;}
int Sort::QuickSortRecursion〔long int parray[], int first=1, int end=Max〕 {if 〔first<end〕
{ int pivot=QuickSortPatition〔parray, first, end〕;
QuickSortRecursion〔parray, first, pivot-1〕;//
左侧子序列排序
}
QuickSortRecursion〔parray, pivot+1, end〕; //
右侧子序列排序
return 0;}
int Sort::QuickSortPatition〔long int r[], int first, int end 〕
{int i=first;int j=end; int temp;
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 页
名师归纳总结
- - - - - - -
第 3 页,共 23 页
精选学****资料
- - - - - - - - -
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; }
}
为轴值记录的最终位置
return i; //i
示意图：
r1,r2,r
3, ⋯ ,ri
- 1,ri,ri+1,
⋯ ,rn
r<ri
轴值 r>ri
<5>挑选排序： 从待排序的记录序列中挑选关键码最小
（或最大） 的记录并将它与序列中
的第一个记录交换位置；
然后从不包括第一个位置上的记录序列中挑选关键码最小
（或最大）
的记录并将它与序列中的其次个记录交换位置；
int Sort::SelectSort〔long int parray[]〕 {
int i,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[in