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

类似叙述题略

外排序用k路归并(k>)是因为k越小归并趟数越多读写外存次数越多时间效率越低故一般应大于最少的路归并若将k路归并的败者树思想单纯用于内排序因其由胜者树改进而来且辅助空间大完全可由堆排序取代故将其用于内排序效率并不高

R: R:

五算法设计题

void BubbleSort(int a[]int n) //相邻两趟向相反方向起泡的冒泡排序算法

{ change=;low=;high=n; //冒泡的上下界

while(low<high && change)

{ change=; //设不发生交换

for(i=low;i<high;i++) //从上向下起泡

if(a[i]>a[i+]){a[i]<>a[i+];change=;} //有交换修改标志change

high; //修改上界

for(i=high;i>low;i) //从下向上起泡

if(a[i]<a[i]){a[i]<>a[i];change=;}

low++; //修改下界

}//while

}//BubbleSort

[算法讨论]题目中向上移理解为向序列的右端而向下移按向序列的左端来处理

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