VB_Python代码对照算法百题（002）

VB_Python代码对照算法百题（002）

算法：冒泡排序

VB代码：

（2015年10月_浙江）16.n个数据的冒泡排序需要经过n-1遍加工，每一遍加工自下而上比较相邻两个数据，把较小者交换到上面。小刘发现：当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。为此，小刘对算法进行优化，编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示这些数据按升序排序后的结果，在标签Label3中显示排序过程的加工遍数。运行效果如第16题图所示。

第16题图

实现上述功能的VB代码如下，但加框处代码有错，请改正。

Dim a(1 To 8) AsInteger

Dim n As Integer

Private SubForm_Load()

'n=8，排序前数据存储在数组a中，并在列表框Listl中显示

'代码略

End Sub

Private SubCommand1_Click()

Dim flag As Boolean'flag值为True表示一遍加工中发生过交换

i = 1

flag = True

DoWhilei

flag = False

For j = n To i + 1 Step -1

If a(j)

k = a(j): a(j) = a(j - 1): a(j - 1) =k

flag = True

End If

Next j

i = i + 1

Loop

Label3.Caption ="排序过程的加工遍数为"+str(i)'（2）

For i = 1 To n

List2.AddItem Str(a(i))

Next i

End Sub

参考答案：

（1）i

（2）Str(i-l)

解析：此算法是优化的冒泡排序，有n个数据需要排序 n – 1次，变式方法是引入标志变量flag，初值为flag = True，进行排序，将标志变量取相反值flag = False，由后至前相邻数据比较，如果“a(j)

当数据有序时，也将执行“i= i + 1”，所以数据有序时，变量i的值多增加1次，确定答案为Str(i-1)。

一般情况如果有n个数据需要排序 n – 1次，但因数据排列的情况差异，可能数据原来就有序，或者在小于n – 1次排序时就已经有序，如果在继续比较排序，将增加排序时间，所以可通过标志变量，即某次排序不发生交换时，说明数据已经有序，退出排序。

排序的前提是排序次数小于n – 1次且数据无序，所循环执行的条件应是两个条件同时成立，要能够正确区分“and”和“or”两个逻辑变量对条件成立的影响。

Python代码如下：

a=[44,38,78,37,96,4,45,69]

n=len(a)

m=0

i=n

flag=True

while i>=1 and flag:

flag = False

for j in range(0,i-1):

if a[j]

a[j],a[j + 1]=a[j + 1],a[j]

flag = True

i=i-1

m=m+1

print('排序过程的加工遍数为'+str(m-1))

a.reverse()

print('排序后的数据为：\n')

print(a)

Python代码运行结果如下：

排序过程的加工遍数为5

排序后的数据为：

[4, 37, 38, 44, 45, 69, 78, 96]