Java-冒泡排序

大家好，欢迎来到IT知识分享网。

在操作数组时，经常需要对数组中的元素进行排序。接下来介绍一种非常常见的排序算法–冒泡排序。

在冒泡排序的过程中，不断地比较数组中相邻的元素，较小者向上浮，较大者向下沉，整个过程和水中气泡上升的原理相似，故称之为冒泡排序。

原理

第一步，从第一个元素开始，将相邻的两个元素进行比较，直到最后两个元素完成比较。如果前面的元素比后面的元素大，则交换它们的位置。整个过程完成后，数组中最后一个元素自然就是最大值，这样也就完成了第一趟的比较。

第二步，除了最后一个元素，将剩余的元素按照第一步的方法进行两两比较，这样就可以将数组中第二大的元素放到倒数第二个位置上。

第三步，以此类推，持续对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较为止。

总体而言，在冒泡排序中，程序的时间复杂度和空间复杂度随着程序的执行，均呈现递减趋势。

代码

public class Example32{
	public static void main(String[] args){
		int[] arr={9, 8, 3, 5, 2};
		System.out.print("冒泡排序前：");
		printArray(arr);								// 打印排序前的数组元素
		bubbleSort(arr);								// 调用排序方法
		System.out.print("冒泡排序后：");
		printArray(arr);								// 打印排序后的数组元素
	}

	// 定义打印数组方法
	public static void printArray(int[] arr){
		for(int i=0; i<arr.length; i++){				// 从第一个数组元素开始遍历数组元素
			System.out.print(arr[i]+" ");				// 输出数组元素，并加空格以控制格式
		}
		System.out.print("\n");							// 完成一次调用后换行
	}

	// 定义冒泡排序方法
	public static void bubbleSort(int[] arr){
		for(int i=0; i<arr.length -1; i++){				// 外层循环，控制总共需要比较的趟数
			for(int j=0; j<arr.length -i -1; j++){		// 内层循环，控制每趟需要比较的次数
				if(arr[j] > arr[j+1]){					// 比较相邻元素
					// 以下三行代码用于交换两个元素
					int temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
			System.out.print("第"+(i+1)+"轮排序后：");	// 每趟执行完后，输出提示信息
			printArray(arr);							// 输出本趟执行后的结果
		}
	}
}

结果

分析

bubbleSort()方法通过一个嵌套for循环实现了冒泡排序。

其中外层循环用来控制比较的趟数，即【数组元素的个数-1】，每一趟比较，都可以确定一个元素的位置，由于最后一个元素不需要比较，因此外层循环的次数为【arr.length-1】。

内层循环用于控制每趟比较的次数，由于变量i在循环的过程中是自增的，因此程序每执行一趟，每次比较的次数递减。

每次比较的过程中，如果前者小于后者，则交换两个元素的位置。

在第一轮比较中，第一个元素【9】为最大值，因此它在每次比较时都会发生位置的交换，直到被放到最后一个位置。第二轮比较中，元素【8】为第二大值，比较过程和第一轮比较类似，直到被放到倒数第二个位置。循环第三轮和第四轮比较，第四轮比较完成后，数组元素已经完成了排序。

其交换过程，类似于A杯子装了可乐，B杯子装了雪碧，现在需要把A杯子的可乐和B杯子的雪碧互换，因此需要拿出C杯子（即临时变量temp）。把B杯子的雪碧倒入C杯子，此时B杯子为空杯；把A杯子的可乐倒入B杯子，此时A杯子为空杯；再将C杯子的雪碧倒入A杯子；此时C杯子为空杯，A杯子为雪碧，B杯子为可乐，即完成了可乐和雪碧的互换。

图例

引用

<- 完 ->