4.1.4　一维数组程序举例

例4-2　求200以内的所有素数。

算法分析：

求素数的算法很多，下面采用经典算法——Eratasthenes筛选法。其算法思路如下：

（1）取最小的数2，并声明它是素数，同时筛去它及它的所有倍数；

（2）取未筛去的数中最小者，声明它是素数，同时筛去它及它的所有倍数；

（3）重复步骤（2），至筛中无数为止，得到所有素数。

筛法实际上是筛去合数，留下素数。

本例可使用数组，让数组下标就是200以内的数，让数组元素的值作为筛去与否的标志，这里设数组元素的初值为0，筛去以后的值变为1。如图4.1.3所示。

图4.1.3　筛法思路：让数组元素值作为筛去的标志

为了提高筛法效率，注意到一个合数n必然有一个小于的正因子，因此一个数若没有小于的正因子，则说明它是一个素数。

根据上述算法，求200以内的素数的程序如下：

上面程序的第12到15行是用筛法求素数的主要程序段。第16至23行用于输出素数。程序的运行结果如图4.1.4所示。

图4.1.4　程序4-2.cpp的运行结果

例4-3　给定由6个整数组成的序列{2，8，4，3，5，9}，将其按从大到小的顺序排列。

算法分析：

首先用一个一维数组存储待排序的序列。

对数组中的数据进行排序是数据处理的基本操作，方法很多，如交换法、选择法、插入法等。本例采用比较简单，又很典型的冒泡排序法进行排序。

冒泡排序法是一种交换排序方法，它的思路是：从序列的一端开始，依次将相邻两个元素比较，当发现它们不合顺序时就进行一次交换，本例需将较小的数调到后面去。这样就像水箱里的气泡一样，每个气泡最后将到达它的平衡位置。

从图4.1.5可见，最小的数第一遍扫描就交换到a[5]中。如果将a[0]视为水底，a[5]视为水面，则：

（1）最小的数2最先浮到水面，交换到a[5]；

（2）次小的数3第二遍扫描交换到a[4]；

（3）再小的数4第三遍扫描交换到a[3]；

依此类推，到第5遍扫描，将第5小的数8交换到a[1]，此时最大的数9自然被存储到a[0]，排序结束。因此6个数排序，共需进行5遍排序。以此类推，对n个数排序，至多只需进行n−1遍排序。

在每遍扫描中，从第1个元素开始，依次与相邻元素进行比较，逆序则交换。

第1遍扫描中，将a[0]与a[1]，a[1]与a[2]，…，a[4]与a[5]比较，比较5次后，最小的元素被交换到a[5]，本遍扫描结束；

第2遍扫描中，将a[0]与a[1]，a[1]与a[2]，…，a[3]与a[4]比较，比较4次后，次小的元素被交换到a[4]，本遍扫描结束；

第3遍扫描中，将a[0]与a[1]，a[1]与a[2]，a[2]与a[3]比较，比较3次后，第三小的元素被交换到a[3]，本遍扫描结束；

可见，第i遍扫描中，需将a[0]与a[1]，a[1]与a[2]，…，a[n−i−1]与a[n−i]比较，比较n−i次后，第i小的元素被交换到a[n−i]，本遍扫描结束。

图4.1.5　冒泡排序法图示

理出上述规律后，不难得出冒泡排序法的算法：

为了表述方便，定义如下3个变量：

（1）待排序的元素个数n，此例中为6；

（2）扫描遍数i，取值为从1到n−1；

（3）第i遍扫描时待比较的元素下标j，取值为从0到n−i−1。

本例可采用一个双重循环，步骤如下：

（1）将待排序的数据放入数组中；

（2）让i从1到n−1，做（3）；

（3）让j从0到n−i−1，做（4）；

（4）比较a[j]与a[j+1]，如果a[j]较小，则将a[j]与a[j+1]交换；

（5）输出排序结果。

参考程序如下：

冒泡排序算法是典型的排序算法，很有用，上面的程序最核心的是第16至第23行。

另外，本程序对无论什么样的数据都会扫描n−1遍，这使得程序在有些情况下效率不高。比如，待排序序列已经排好序，而本程序也会进行n−1遍扫描。实际上，本程序稍作修改，就可以避免这种无用的扫描。

只需用一个变量changed表示一遍扫描中是否进行了交换。在每一遍扫描开始时，将其置为0，表示未交换，在扫描中如果进行了交换，则将此变量置为1，本遍扫描完成后，如果changed的值为0，则表示本遍扫描中未进行交换，因此可退出扫描，输出结果。

下面是修改后的程序。

常见的编程错误4.1

数组的下标从0开始，例如数组的第7个元素的下标是6。

在数组的初始化列表中提供比数组元素个数多的初始值。

忘记初始化应该初始化的数组元素。

引用超出数组边界的元素。

良好的编程习惯4.1

为了易读、易修改和方便注释，我们倾向于每次定义一个数组。

把每个数组的大小定义为符号常量，而不是字面上的常量，可使程序更清晰。