数组排序算法
数组有很多常用的算法，本节将介绍常用的排序算法，包括冒泡排序、直接选择排序和反转排序。
冒泡排序
在程序设计中，经常需要对一组数列进行排序，这样更加方便统计与查询。程序常用的排序方法有冒泡排序、选择排序和反转排序等。本节将讲解冒泡排序方法，这种排序方法以其简洁的思想和实现方法备受开发人员青睐，是广大学习者最先接触的一种排序算法。
冒泡排序是最常用的数组排序算法之一，它排序数组元素的过程总是将较小的数往前放、较大的数往后放，类似水中气泡往上升的动作，因此称为冒泡排序。
基本思想
冒泡排序的基本思想是对比相邻的元素值，如果满足条件，就交换元素值，把较小的元素移动到数组前面，把较大的元素移动到数组后面（也就是交换两个元素的位置），这样较小的元素就像气泡一样从底部上升到顶部。
算法示例
冒泡算法由双层循环实现，其中外层循环用于控制排序轮数，一般为要排序的数组长度减 1 次，因为最后一次循环只剩下一个数组元素，不需要对比，同时数组已经完成排序了。而内层循环主要用于对比数组中每个邻近元素的大小，以确定是否交换位置，对比和交换次数随排序轮数而减少。例如，一个拥有 6 个元素的数组，在排序过程中每一次循环的排序过程和结果如图5.4所示。
第 1 轮外层循环时把最大的元素值 63 移动到了最后面（相应地，比 63 小的元素向前移动，类似气泡上升）；第 2 轮外层循环不再对比最后一个元素值 63，因为它已经被确认为最大（不需要上升），应该放在最后，需要对比和移动的是其他剩余元素，这次将元素 24 移动到了 63 的前一个位置。其他循环将以此类推，继续完成排序任务。
算法实现
下面介绍冒泡排序的具体用法。
【例5.12】冒泡排序（实例位置：资源包\TM\sl\5\12）
在项目中创建 BubbleSort 类，这个类的代码将对一个 int 型的一维数组中的元素进行冒泡排序。实例代码如下：
public class BubbleSort {
public static void main(String[] args) {
// 创建一个数组，这个数组元素是乱序的
int[] array = { 63, 4, 24, 1, 3, 15 };
// 创建冒泡排序类的对象
BubbleSort sorter = new BubbleSort();
// 调用排序方法将数组排序
sorter.sort(array);
}
/**
* 冒泡排序
*
* @param array 要排序的数组
*/
public void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 比较相邻两个元素，较大的数往后冒泡
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j]; // 把第一个元素值保存到临时变量中
array[j] = array[j + 1]; // 把第二个元素值保存到第一个元素单元中
array[j + 1] = temp; // 把临时变量（也就是第一个元素原值）保存到第二个元素中
}
}
}
showArray(array); // 输出冒泡排序后的数组元素
}
/**
* 显示数组中的所有元素
*
* @param array 要显示的数组
*/
public void showArray(int[] array) {
for (int i : array) { // 遍历数组
System.out.print(" >" + i); // 输出每个数组元素值
}
System.out.println();
}
}运行结果如下：
>1 >3 >4 >15 >24 >63从实例的运行结果中可以看出，数组中的元素已经按从小到大的顺序排列好了。冒泡排序的主要思想就是：把相邻两个元素进行比较，如果满足一定条件则进行交换（如判断大小或日期前后等），每次循环都将最大（或最小）的元素排在最后，下一次循环是对数组中其他的元素进行类似操作。
直接选择排序
直接选择排序属于选择排序的一种，它的排序速度要比冒泡排序快一些，也是常用的排序算法，初学者应该掌握。
基本思想
直接选择排序的基本思想是将指定排序位置元素与其他数组元素分别对比，如果满足条件就交换元素值。注意这里与冒泡排序的区别，不是交换相邻元素，而是把满足条件的元素与指定的排序位置元素进行交换（如从最后一个元素开始排序），这样排序好的位置被逐渐扩大，直至整个数组都变成已排序好的格式。
这就好比有一名小学生，从包含数字1～10的乱序的数字堆中分别选择合适的数字，组成一个1～10的排序，而这名学生首先从数字堆中选出1，放在第一位，然后选出2（注意这时数字堆中已经没有1了）放在第二位，以此类推，直到其找到数字9，放到8的后面，最后剩下10，就不用选择了，直接放到最后就可以。
与冒泡排序相比，直接选择排序的交换次数要少很多，因此速度会快些。
算法示例
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序地放在已排好序的数列的最后，直到全部待排序的数据元素被排完。例如：
初始数组资源 【63 4 24 1 3 15】
第一趟排序后 【15 4 24 1 3 】 63
第二趟排序后 【15 4 3 1】 24 63
第三趟排序后 【1 4 3】 15 24 63
第四趟排序后 【1 3】 4 15 24 63
第五趟排序后 【1】 3 4 15 24 63算法实现
下面介绍直接选择排序的具体用法。
【例5.13】直接选择排序（实例位置：资源包\TM\sl\5\13）
在项目中创建 SelectSort 类，这个类的代码将对一个 int 型的一维数组中的元素进行直接选择排序。实例代码如下：
/**
* 直接选择排序算法实例
*/
public class SelectSort {
public static void main(String[] args) {
// 创建一个数组，这个数组元素是乱序的
int[] array = { 63, 4, 24, 1, 3, 15 };
// 创建直接排序类的对象
SelectSort sorter = new SelectSort();
// 调用排序对象的方法将数组排序
sorter.sort(array);
}
/**
* 直接选择排序
*
* @param array 要排序的数组
*/
public void sort(int[] array) {
int index;
for (int i = 1; i < array.length; i++) {
index = 0;
for (int j = 1; j <= array.length - i; j++) {
if (array[j] > array[index]) {
index = j;
}
}
// 交换在位置array.length-i和index(最大值)上的两个数
int temp = array[array.length - i]; // 把第一个元素值保存到临时变量中
array[array.length - i] = array[index]; // 把第二个元素值保存到第一个元素单元中
array[index] = temp; // 把临时变量也就是第一个元素原值保存到第二个元素中
}
showArray(array); // 输出直接选择排序后的数组元素
}
/**
* 显示数组中的所有元素
*
* @param array 要显示的数组
*/
public void showArray(int[] array) {
for (int i : array) { // 遍历数组
System.out.print(" >" + i); // 输出每个数组元素值
}
System.out.println();
}
}运行结果如下：
>1 >3 >4 >15 >24 >63反转排序
顾名思义，反转排序就是以相反的顺序把原有数组的内容进行重新排序。反转排序算法在程序开发中也经常使用。
算法示例
反转排序是对数组两边的元素进行替换，因此 for 循环只需要循环数组长度的半数次，如数组长度为 7，那么 for 循环只需要循环 3 次。例如：
初始数组资源 【10 20 30 40 50 60】
第一趟排序后 60 【20 30 40 50】 10
第二趟排序后 60 50 【30 40】 20 10
第三趟排序后 60 50 40 30 20 10算法实现
下面介绍反转排序的具体用法。
【例5.14】反转排序（实例位置：资源包\TM\sl\5\14）
在项目中创建 ReverseSort 类，这个类的代码将对一个 int 型的一维数组中的元素进行反转排序。实例代码如下：
/**
* 反转排序算法实例
*/
public class ReverseSort {
public static void main(String[] args) {
// 创建一个数组
int[] array = { 10, 20, 30, 40, 50, 60 };
// 创建反转排序类的对象
ReverseSort sorter = new ReverseSort();
// 调用排序对象的方法，将数组反转
sorter.sort(array);
}
/**
* 反转排序
*
* @param array 要排序的数组
*/
public void sort(int[] array) {
System.out.println("数组原有内容：");
showArray(array); // 输出排序前的数组元素
int temp;
int len = array.length;
for (int i = 0; i < len / 2; i++) {
temp = array[i];
array[i] = array[len - 1 - i];
array[len - 1 - i] = temp;
}
System.out.println("数组反转后内容：");
showArray(array); // 输出排序后的数组元素
}
/**
* 显示数组中的所有元素
*
* @param array 要显示的数组
*/
public void showArray(int[] array) {
for (int i : array) { // 遍历数组
System.out.print("\t" + i); // 输出每个数组元素值
}
System.out.println();
}
}运行结果如下：
数组原有内容：
10 20 30 40 50 60
数组反转后内容：
60 50 40 30 20 10编程训练（答案位置：资源包\TM\sl\5\编程训练）
【训练7】成绩排名（一） 10名学生在一次英语竞赛中的成绩分别为71、89、67、53、78、64、92、56、74和85，使用冒泡排序编写一个程序，将这10名学生的英语竞赛成绩由小到大进行排序。
【训练8】成绩排名（二） 将“训练7”中的10名学生的英语竞赛成绩由大到小进行排序。