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

() ① ②A[j]>A[j+] ③b:=true ()冒泡排序 ()次比较次交换

() n(n)/次比较n(n)/次交换(相当n(n)/次移动)本题中n=故有次比较和交换(相当次移动)

答此排序为双向起泡排序从前向后一趟排序下来得到一个最大值若其中发生交换则再从后向前一趟排序得到一个最小值

一趟

二趟 三趟

四趟 五趟

六趟 七趟

对冒泡算法而言初始序列为反序时交换次数最多若要求从大到小排序则表现为初始是上升序

证明起泡排序思想是相邻两个记录的关键字比较若反序则交换一趟排序完成得到一个极值由题假设知Rj在Ri之前且Kj>Ri即说明Rj和Ri是反序设对于Ri之前全部记录Ri(其中包括Kj)中关键字最大为Kmax则Kmax≥Kj故经过起泡排序前i次后Ri的关键字一定为Kmax又因Kmax≥Kj>Ri故Ri和Ri为反序由此可知Ri和Ri必定交换证毕

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