冒泡法排序实例：产生并排序5个两位整数数组

【例5-7】冒泡法排序。

用随机函数产生5个两位整数保存到数组中，然后将数组按由小到大顺序排序并输出。

按“三步法”原则分析如下。

做什么

1）用随机函数产生5个两位整数并输出。

2）将数组排序。

3）将排序后的数组输出。

所以窗体上只需要一个命令按钮即可。

怎么做

对于n个元素，冒泡法描述如下。

1）第1遍，对于1～n个元素，从第1个元素开始，将相邻的两个数依次进行比较，小的上升（前移），大的下沉（后移），经n−1次比较后，最大的数下沉到最下面。

2）第2遍，对于1～n−1个元素，从第1个元素开始，将相邻的两个数依次进行比较，小的上升，大的下沉，经n−2次比较后，最大的数下沉到最下面。

3）其余类推，经过n−1遍比较后，排序完成。

为了便于分析，设定数组下标从1开始，数组个数为5。筛选过程如下。

●第1遍（用i记录遍数，i初始为1）：

a（1）与a（2）比较，若a（1）＞a（2），则交换a（1）、a（2）；然后a（2）与a（3）比较，若a（2）＞a（3），则交换a（2）、a（3）；然后a（3）与a（4）比较，若a（3）＞a（4），则交换a（3）、a（4）；然后a（4）与a（5）比较，若a（4）＞a（5），则交换a（4）、a（5）。比较完后，a（5）即为5个元素中的最大元素。

●第2遍（i修改为2）：

对前4个元素进行比较排序，a（1）与a（2）比较，若a（1）＞a（2），则交换a（1）、a（2）；然后a（2）与a（3）比较，若a（2）＞a（3），则交换a（2）、a（3）；然后a（3）与a（4），若a（3）＞a（4）比较，则交换a（3）、a（4）。比较完后，a（4）即为前4个元素中的最大元素。

●第3遍（i修改为3）：

对前3个元素进行比较排序：a（1）与a（2）比较，若a（1）＞a（2），则交换a（1）、a（2）；然后a（2）与a（3）比较，若a（2）＞a（3），则交换a（2）、a（3）。比较完后，a（3）即为前3个元素中的最大元素。

●第4遍（i修改为4）：

对前2个元素进行比较排序，a（1）与a（2）比较，若a（1）＞a（2），则交换a（1）、a（2）。比较完后，a（2）即为前2个元素中的最大元素。

经过4遍比较后，排序完成。

通过分析，可以得出如下结论。

1）对于n个数，需要比较n−1遍，每遍找出一个较大者，所以应该需要一个循环来控制遍数。(www.xing528.com)

2）在每遍比较过程中，需要进行多次比较才能把最大数下沉到最下面，所以需要一个循环来控制每遍比较过程的比较次数。而比较次数与执行第几遍排序有关，也就是与遍数i有关。

3）在每遍比较过程中，都是相邻两个元素进行比较。所以确定前面元素的下标，就可以确定与它相邻的下一个元素的下标。有两种表示方法：“a（j）与a（j+1）比较”或“a（j−1）与a（j）比较”。前一种方法在遍历数组时经常用到，这里用“a（j）与a（j+1）比较”表示方法。

由此得出需要的遍数、每遍比较次数对应关系见表5-3。

表5-3 冒泡法排序i，j对应关系

推广到n个元素：

●遍数i的变化范围为1～n−1。

●控制比较次数j的变化范围为1～n−i。

本例的步骤描述如下：

1）用随机函数产生5个数保存到数组a中。

2）初始化变量i=1。

3）判断i值，如果i＜=4，则执行第4）步；否则执行第9）步。

4）初始化变量j=1。

5）判断j值，如果j＜=5−i，则执行第6）步；否则执行第8）步。

6）如果a（j）＞a（j+1），则交换a（j）、a（j+1）。

7）j值增1，返回第5）步。

8）i值增1，返回第3）步。

9）输出排序后的数组。

实现

完整代码如下。

运行结果如图5-8所示。

图5-8 冒泡法排序