数据结构考研分类复习真题 第十章 答案[34]

typedef struct

{ int num; float score; }RecType;

void SelectSort(RecType R[]int n)

{ for(i=; i<n; i++)

{ //选择第i大的记录并交换到位

k=i; //假定第i个元素的关键字最大

for(j=i+;j<=n;j++) //找最大元素的下标

if(R[j]score>R[k]score) k=j;

if(i!=k) R[i] <>R[k]; //与第i个记录交换

}//for

for(i=; i<=n; i++) //输出成绩

{ printf(%d%fR[i]numR[i]score); if(i%==) printf(\n);}

}//SelectSort

typedef struct

{ int key; datatype info}RecType

void CountSort(RecType a[]b[]int n) //计数排序算法将a中记录排序放入b中

{ for(i=;i<n;i++) //对每一个元素

{ for(j=cnt=;j<n;j++)

if(a[j]key<a[i]key) cnt++; //统计关键字比它小的元素个数

b[cnt]=a[i];

}

}//Count_Sort

() 对于有n个记录的表关键码比较n次

() 简单选择排序算法比本算法好简单选择排序比较次数是n(n)/且只用一个交换记录的空间而这种方法比较次数是n且需要另一数组空间

[算法讨论]因题目要求针对表中的每个记录扫描待排序的表一趟所以比较次数是n次若限制对任意两个记录之间应该只进行一次比较则可把以上算法中的比较语句改为

for(i=;i<n;i++) a[i]count=;//各元素再增加一个计数域初始化为

for(i=;i<n;i++)

for(j=i+;j<n;j++)

if(a[i]key<a[j]key) a[j]count++; else a[i]count++;

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []