JAVA排序算法-冒泡排序

在程序设计中,经常需要将一组数列进行排序,这样更加方便统计 与查询。程序常用的排序方法有冒泡排序、选择排序和快速排序等。本节将介绍冒泡排序方法,它以简洁的思想与实现方法而备受青睐,是广 大学习者最先接触的一种排序算法。

冒泡排序是最常用的数组排序算法之一,它排序数组元素的过程总 是将小数往前放、大数往后放,类似水中气泡往上升的动作,所以称作 冒泡排序。

1.基本思想

冒泡排序的基本思想是对比相邻的元素值,如果满足条件就交换元 素值,把较小的元素移动到数组前面,把大的元素移动到数组后面(也 就是交换两个元素的位置),这样较小的元素就像气泡一样从底部上升到顶部。

2.算法示例

冒泡算法由双层循环实现,其中外层循环用于控制排序轮数,一般为要排序的数组长度减1次,因为最后一次循环只剩下一个数组元素, 不需要对比,同时数组已经完成排序了。而内层循环主要用于对比数组 中每个邻近元素的大小,以确定是否交换位置,对比和交换次数随排序 轮数而减少。例如,一个拥有6个元素的数组,在排序过程中每一次循 环的排序过程和结果如图所示。

冒泡算法-6个元素数组的排序过程
6个元素数组的排序过程

第一轮外层循环时把最大的元素值63移动到了最后面(相应地,比 63小的元素向前移动,类似气泡上升),第二轮外层循环不再对比最后 一个元素值63,因为它已经被确认为最大(不需要上升),应该放在最 后,需要对比和移动的是其他剩余元素,这次将元素24移动到了63的前 一个位置。其他循环将以此类推,继续完成排序任务。

3.算法实现

下面来介绍一下冒泡排序的具体用法。

【例】在项目中创建BubbleSort类,这个类的代码将实现冒泡 排序的一个演示,其中排序使用的是正排序,读者可以根据本实例编写 一个倒排序的例子。

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) {// foreach格式遍历数组
			System.out.print(" >" + i);// 输出每个数组元素值
		}
		System.out.println();
	}
}
运行结果如图6.16所示。
运行结果如图所示。

从实例的运行结果来看,数组中的元素已经按从小到大的顺序排列 好了。冒泡排序的主要思想就是:把相邻两个元素进行比较,如满足一定条件则进行交换(如判断大小或日期前后等),每次循环都将最大 (或最小)的元素排在最后,下一次循环是对数组中其他的元素进行类 似操作。

发表评论