小军学习了冒泡排序算法后觉得算法还有优化的余地：假设区间[1，i]内的元素已经有序，接下来对[i+1，n]所有元素进行扫描比较，扫描完后记住最后一次交换的位置last_exchange，这个位置说明了区间[i+1，last_exchange-1]内的元素是有序的。标准冒泡排序算法下一遍的扫描区间是[i+2，n]，而有了last_exchange位置信息后，下一遍的扫描区间只要[last_exchange，n]即可。小军用VB实现了该算法，运行的界面如图所示。

Const maxn = 1000

Dim a(0 To maxn) As Long

Private Sub Form_Load()

′产生maxn个不相同的数据，并把他存储在a数组中，代码略

End Sub

Private Sub Command1_Click()

Dim i As Long, j As Long, tmp As Long, cnt As Long

Dim last_exchange As Integer ′记录最后一次交换位置

Dim tmp_pos As Integer  ′本次交换的位置

cnt = 0: i = 1

last_exchange = 0: tmp_pos = 1

Do While        ′改错

  last_exchange = tmp_pos

  For j = maxn To last_exchange + 1 Step -1

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

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

                            

      cnt = cnt + 1

    End If

  Next j

  i = tmp_pos

Loop

′输出，代码略

End Sub