两中种简单排序算法分析

通过上面分析，可以归纳出用直接插入排序算法对数组 a 进行递增排序的步骤：

（1） 将 a(1) 直接插入有序区；

（2） 在有序区中进行搜索，找到下一个待排序记录的插入位置（插入点）；

（3） 将插入点右边的记录整体向右移动一个位置；

（4） 插入待排序记录；

（5） 重复执行（ 2 ）到（ 4 ）步，直到无序区中的所有记录全部插入到有序区。

参考程序如下：

CLS

DIM a(10) AS INTEGER

rem 输入数据

FOR i = 1 TO 10

INPUT a(i)

NEXT i

rem 直接插入排序

FOR i = 2 TO 10

rem 设置监视哨 a(0) （监视哨有两个好处：一是在记录右移的过程中，可以防止元素 a(i) 的值丢失；二是可以监视数组下标是否出界）

a(0) = a(i)

rem 搜索插入位置

k = i - 1

WHILE a(i) < a(k)

k = k - 1

WEND

rem 移动记录

j = i - 1

DO UNTIL j < k + 1

a(j + 1) = a(j)

j = j - 1

LOOP

rem 出入待排序记录

a(k + 1) = a(0)

NEXT i

rem 输出数据

FOR i = 1 TO 10

PRINT a(i);

NEXT i

END

上面的直接排序算法，我们是将搜索插入位置和移动记录两个过程分开，即先执行第（ 2 ）步，完成插入位置的确定问题，再执行第（ 3 ）步，将插入点右边的记录整体向右移动一个位置。实际上，我们可以将这两个过程结合起来，交替进行。参考程序如下：

CLS

DIM a(10) AS INTEGER

FOR i = 1 TO 10

INPUT a(i)

NEXT i

rem 直接插入排序

FOR i = 2 TO 10

a(0) = a(i)

j = i - 1

x = a(i)

WHILE x < a(j)

a(j + 1) = a(j)

j = j - 1

WEND

a(j + 1) = a(0)

NEXT i

FOR i = 1 TO 10

PRINT a(i);

NEXT i

END

冒泡排序的基本思想是：将要排序的记录竖直放置，按从上到下的顺序对记录两两进行比较，保证轻者（要害字小的记录）在上，重者（要害字大的记录）在下；在比较的过程中，假如发现有违反“轻者在上，重者在下”这条原则的，就将两个记录进行交换；就像水中的气泡一样，轻的总是往上漂；这样对记录进行扫描，当完成第一趟扫描以后，最大的记录自然会沉到最底部。接着对记录进行第二趟扫描、第三趟扫描、……直到所有记录都是轻者在上，重者在下为止。

还是以上面对 10 个学生的信息技术考试成绩进行递增排序为例，用冒泡思想进行排序的过程是：首先将 a(1) 和 a(2) 进行比较，若 a(1)>a(2) ，则将 a(1) 和 a(2) 进行交换，然后比较 a(2) 和 a(3) 、 a(3) 和 a(4) 、……依此类推，直到将最后两个记录 a(9) 和 a(10) 进行比较为止，如图。

上述过程称为第 1 趟冒泡排序，其结果是使得要害字最大的记录沉到数组的最底部（即被安置到最后一个记录 a(10) 的位置）。

然后进行第 2 趟冒泡排序（对前 9 个记录进行同样的操作），使得要害字次大的记录被安置到倒数第 2 个记录 a(9) 的位置。依此类推，进行第 3 趟、第 4 趟、……如图 3

显然，冒泡排序主要进行两个操作：比较和交换。

这里还有一个要害问题需要考虑：排序过程需要进行多少趟，即判别冒泡排序结束的条件是什么？

如图，我们可以假设再进行第 10 趟排序，很轻易看出，第 10 趟排序将不会进行任何交换操作，因为经过第 9 趟排序之后，数组中的数据已经递增有序了。据此，我们不妨将判别冒泡排序结束的条件定为：在一趟排序过程中没有进行过记录的交换。

用冒泡排序算法对 10 个学生的信息技术考试成绩进行递增排序的参考程序如下：

CLS

DIM a(10) AS INTEGER

rem 输入数据

FOR i = 1 TO 10

INPUT a(i)

NEXT i

rem 冒泡排序

i = 1

exchange = 1

rem 初始化标志 exchange （用来标识是否进行过交换操作， exchange=1 表示进行过交换操作， exchange=0 表示未进行过交换操作）

DO UNTIL i > 10 OR exchange = 0

exchange = 0

FOR j = 1 TO 10 - i

IF a(j + 1) < a(j) THEN

a(0) = a(j + 1)

a(j + 1) = a(j)

a(j) = a(0)

rem 交换 a(j+1) 和 a(j)

exchange = 1

END IF

NEXT j

i = i + 1

LOOP

rem 输出数据

FOR i = 1 TO 10

PRINT a(i);

NEXT i

END

结束语： 对 10 个学生的信息技术考试成绩按递增排序，这样一个简简单单的问题，这里随随便便就给出了三种解决办法。由此可见，很多问题，非凡是程序设计问题，它的解决办法不是一成不变的。在学习程序设计的过程中，我们要善于打破固定的思维模式，把学习的重点放到对问题解决方法的学习上来。　

注：此文刊于《中学生电脑》杂志2003年第1期