数组逆序排序算法

4.1.4　一维数组程序举例

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

求素数的算法很多，经典算法是Eratasthenes筛选法。其算法思路为

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

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

（3）重复步骤（2），得到所有素数。

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

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

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

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

根据上述算法，求200以内的素数的参考程序为

程序的运行结果如图4.1.4所示。

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

程序的第12行

　　for (d=2;d<=sqrt(200);d++)

每次循环都需要计算sqrt(200)，从效率方面考虑，可以增加变量pri-num的定义并进行赋值：

　　pri-num= sqrt(200)；

将第12行改为

　　for (d=2;d<=pri_num;d++)

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

使用一维数组存储待排序的序列。

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

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

最小的数第一遍扫描就交换到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表示。

图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）输出排序结果。

参考程序为

程序进行从大到小的排列，如果将第18行

　　if (a[j]<a[j+1])

修改为

　　if (a[j]>a[j+1])则进行从小到大的排列。

另外，需要扫描n−1遍，在有些情况下效率不高。例如，待排序序列已经排好序，而本程序也会进行n−1遍扫描。稍作修改，就可以避免这种无用的扫描。

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

程序修改为

常见的编程错误4.1

●数组的下标从0开始。

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

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

●数组下标越界。

良好的编程习惯4.1

●为了易读、易修改和方便注释，多个数组分行进行定义。

●数组的大小定义使用符号常量（而不是字面常量），可使程序更清晰。