首页 > 试题广场 >

阅读下列排序算法,并与已学算法相比较,讨论算法中基本操作的执

[问答题]

阅读下列排序算法,并与已学算法相比较,讨论算法中基本操作的执行次数。

void sort(SqList &r, int n)
{
i=1;
while (i<n-i+1)
{
min = max = 1;
for(j=i+1; j<=n-i+1; ++j)
{
if(r[j].key<r[min].key)
min = j;
else if(r[j].key>r[max].key)
max = j;
}//for
if(min!=i)
r[min]↔r[i];
if(max!=n-i+1)
{
if(max==i)
r[min]↔r[n-i+1];
else
r[max]↔r[n-i+1];
}//if
i++;
}//while
}//sort

这是一个双向选择排序算法,每次选择关键码最小的记录放在前面,同时选择关键码最大的记录放在后面。比较n*(n-1)\2次。最好情况移动记录0次,最坏情况大约移动记录3n次。
发表于 2021-03-10 20:25:13 回复(0)