用选择法排序多位整数并输出

【例5-6】选择法排序。

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

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

做什么

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

2）将数组排序。

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

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

怎么做

选择法描述如下。

1）对于n个元素，从中选择最小元素与第1个元素交换。

2）除去第1个元素，从剩下的n-1个元素中选择最小元素与第2个元素交换。

3）其余类推，选择n−1次后，排序完成。

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

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

从5个元素中找出最小元素，可以参考例5-4，只是改为找出最小元素。

先假设第1个元素是最小的，把下标1保存到变量t，然后令变量j=2，即取第2个元素a（j）与a（t）进行比较。如果a（j）小于a（t），则把j值赋值给t，然后j值增1为3，即取第3个元素a（j）与a（t）进行比较。其余类推，当j=5，即最后一个元素比较完毕后，t即为这5个元素中最小元素的下标。这时a（t）与a（1）互换（实际上就是a（t）与a（i）互换），那么5个元素中的最小元素就排到了第1位。

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

采用相同的方法，从剩下的4个元素中找出最小元素与第2个元素互换。

先假设第2个元素是最小的，即下标2保存到变量t中，然后令变量j=3，即取第3个元素a（j）与a（t）进行比较。如果a（j）小于a（t），则把j值赋值给t，然后j值增1为4，即取第4个元素a（j）与a（t）进行比较。其余类推，当j=5，即最后一个元素比较完毕后，t即为后面4个元素中最小元素的下标。这时a（t）与a（2）互换（实际上就是a（t）与a（i）互换），那么后面4个元素中最小元素就排到了第2位。

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

采用相同的方法，从剩下的3个元素中找出最小元素与第3个元素互换。

先假设第3个元素是最小的，即下标3保存到变量t，然后令变量j=4，即取第4个元素a（j）与a（t）进行比较。如果a（j）小于a（t），则把j值赋值给t，然后j值增1为5，即取第5个元素a（j）与a（t）进行比较。当最后一个元素比较完毕后，t即为后面3个元素中最小元素的下标。这时a（t）与a（3）互换（实际上就是a（t）与a（i）互换），那么后面3个元素中最小元素就排到了第3位。

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

采用相同的方法，从剩下的2个元素中找出最小元素与第4个元素互换。

先假设第4个元素是最小的，即下标4保存到变量t中，然后令变量j=5，即取第5个元素a（j）与a（t）进行比较。如果a（j）小于a（t），则把j值赋值给t，当最后一个元素比较完毕后，t即为后面2个元素中最小元素的下标。这时a（t）与a（4）互换（实际上就是a（t）与a（i）互换），那么后面2个元素中最小元素就排到了第4位。

经过4遍比较后，已经把4个数按从小到大顺序排好，剩下最后一个元素a（5），就是所有元素中的最大元素，无须再进行比较了，至此5个元素排序完毕。

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

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

2）在每遍比较过程中，需要多个元素分别和a（t）进行比较，这也需要用循环来控制。

3）在每遍比较过程中，比较次数是变化的，这个变化与查找第几个最小元素有关，也就是与遍数有关。

4）由于下标是从1开始的，所以每遍比较完毕后，t就是最小数的下标，而与a（t）进行交换的元素即为遍数i，也就是正在找的第几个最小元素。

由此得出需要的遍数、每遍比较的次数以及与t的对应关系，见表5-2。

表5-2 选择法排序i，j对应关系

推广到n个元素：

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

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

本例的步骤描述如下。

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

2）初始化变量i=1。

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

4）假定a（i）为最小值，把i赋值给t。

5）初始化变量j=i+1。

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

7）如果a（j）＜a（t），则t=j，继续向下执行。

8）j值增1，返回第6）步。

9）a（i）与a（t）互换。

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

11）输出排序后的数组。

实现

完整代码如下：

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

图5-7 选择法排序