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

Do  While i <= n – 1 Or flag = True      ‘（1）            

   flag = False

   For j = n To i + 1 Step -1

      If a(j) < a(j – 1) Then

         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 <= n – 1 And flag = True

（2）Str(i-l)

 

解析：此算法是优化的冒泡排序，有n个数据需要排序 n – 1次，变式方法是引入标志变量flag，初值为flag = True，进行排序，将标志变量取相反值flag = False，由后至前相邻数据比较，如果“a(j) < a(j – 1)”即进行交换，并且flag = True，如果当某次排序未发生交换，即“a(j) < a(j – 1)”在某次排序时始终不成立，说明数据已经有序，标志变量flag为False，退出循环，所以排序的循环条件是i <= n – 1 和flag = True同时成立，用于连接的逻辑运算符应为and。

  当数据有序时，也将执行“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 + 1] :

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

            flag = True     

    i=i-1

    m=m+1

print(‘排序过程的加工遍数为’+str(m  ))

a.reverse()

print(‘排序后的数据为：n’)

print(a)

Python代码运行结果如下：

排序过程的加工遍数为5

排序后的数据为：

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