Java程序设计-数组排序及快速、选择、合并排序示例

排序（sorting）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作25%的时间都在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。现实生活中，有时会要求对一些数据由高到低或者由低到高地进行排列，这时就要用到数组排序算法。排序算法是算法和数据结构中的主要内容。本节将主要介绍选择排序、冒泡排序、插入、快速、合并排序等算法。

1. 冒泡排序法

冒泡排序的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就像水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此，要在排序过程中设置一个标志flag 判断元素是否进行过交换，从而减少不必要的比较。

图3.2 演示了一个冒泡过程的例子。

图3.2　冒泡过程示例

【例3.11】下面用数组实现冒泡法排序程序演示，如文件3-11 所示。

文件3-11　Example11.java

执行结果

【例3.12】实现冒泡排序每轮排序结果输出案例，如文件3-12 所示。

文件3-12　Example12.java

执行结果

2. 快速排序法

快速排序（quick sorting）是对冒泡排序的一种改进，由C.A.R.Hoare 在1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图3.3 演示了快速排序原理。

图3.3　快速排序执行过程

【例3.13】用下面的程序案例演示快速排序法过程，如文件3-13 所示。

文件3-13　Example13.java

执行结果

3. 选择排序法

选择式排序法也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，经过和其他元素重整，再依原则交换位置后达到排序的目的。

选择式排序又可分为两种：

① 选择排序法（selection sorting）；

② 堆排序法（heap sorting）。

选择排序也是一种简单的排序方法。它的基本思想是：第一次从R[0]～R[n-1]中选取最小值，与R[0]交换，第二次从R[1]～R[n-1]中选取最小值，与R[1]交换，第三次从R[2]～R[n-1]中选取最小值，与R[2]交换，……，第i 次从R[i-1]～R[n-1]中选取最小值，与R[i-1]交换，……，第n-1 次从R[n-2]～R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1 次，得到一个按排序码从小到大排列的有序序列。

例如，给定n=7，数组R 中的7 个元素的排序码为：(15，14，22，30，37，15，11)，选择排序过程如图3.4 所示。

图3.4　选择排序过程

【例3.14】利用选择排序算法思想编写一段代码实现上述排序原理案例，假设数据初态为（8，3，2，1，7，4，6，5），如文件3-14 所示。

文件3-14　Example14.java

执行结果

4. 插入排序法。

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。(www.xing528.com)

插入式排序法又可分为3 种：插入排序法（insertion sorting）、希尔排序法（shell sorting）（欧洲人员喜欢使用）、二叉树排序法（binary-tree sorting）

插入排序（insertion sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始有序表只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入有序表中的适当位置，使之成为新的有序表。

插入排序每一重循环的目的是将未排序部分的一个元素插入已排序部分中去。

例如，数组R 中的6 个元素初始状态为：(5，4，10，20，12，3)，插入排序原理过程如图3.5 所示。

图3.5　插入排序过程

【例3.15】实现插入式排序法案例源代码，假设数据初态为（23，15，-13，62，5，-23，0，17），如文件3-15 所示。

文件3-15　Example15.java

执行结果

5. 其他排序法—— 合并排序法

合并排序法（merge sorting）是外部排序最常使用的排序方法。若数据量太大无法一次完全加载内存，可使用外部辅助内存来处理排序数据，主要应用在文件排序。

排序方法如下：

首先，图3.6 所示将欲排序的数据分别存在数个文件大小可加载内存的文件中。然后，针对各个文件分别使用“内部排序法”将文件中的数据排序好写回文件。最后，对所有已排序好的文件两两合并，直到所有文件合并成一个文件后，则数据排序完成。

（1）将已排序好的A、B 合并成E，C、D 合并成F，E、F 的内部数据分别均已排好序。

（2）将已排序好的E、F 合并成G，G 的内部数据已排好序。

（3）四个文件A、B、C、D 数据排序完成。

图3.6　合并排序法示例

【例3.16】合并排序法案例源代码，假设数据初态为（5，4，10，8，7，9），如文件3-16 所示。

文件3-16　Example16.java

执行结果

5. 查找

在Java 中，常用的查找方式有两种：

① 顺序查找（最简单，效率最低）；

② 二分查找。

【例3.17】下面通过一个案例，用数组实现二分查找算法，如文件3-17 所示。

文件3-17　Example17.java

执行结果

一维数组小结

（1）数组可存放同一类型数据；

（2）简单数据类型(int，float)数组，可直接赋值；

（3）对象数组在定义后，赋值时需要再次为每个对象分配空间[即：new 对象]；

（4）数组大小必须事先指定；

（5）数组名可以理解为指向数组首地址的引用；

（6）数组的下标是从0 开始编号的。