冒泡排序(Bubble Sort)

冒泡排序是一种交换排序。

基本思想

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

思路

代码实现

package com.nanzx.sort;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int arr[] = { 6, 3, 5, 7, 0 };
		int temp;  //临时变量，用于交换；
		// 第一趟排序，就是将第一大的数排在倒数第一位
		for (int j = 0; j < arr.length - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("第一趟排序后的数组");
		System.out.println(Arrays.toString(arr));

		// 第二趟排序，就是将第二大的数排在倒数第二位
		for (int j = 0; j < arr.length - 2; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("第二趟排序后的数组");
		System.out.println(Arrays.toString(arr));

		// 第三趟排序，就是将第三大的数排在倒数第三位
		for (int j = 0; j < arr.length - 3; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("第三趟排序后的数组");
		System.out.println(Arrays.toString(arr));

		// 第四趟排序，就是将第4大的数排在倒数第4位
		for (int j = 0; j < arr.length - 4; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		System.out.println("第四趟排序后的数组");
		System.out.println(Arrays.toString(arr));
	}
}

运行结果

第一趟排序后的数组
[3, 5, 6, 0, 7]
第二趟排序后的数组
[3, 5, 0, 6, 7]
第三趟排序后的数组
[3, 0, 5, 6, 7]
第四趟排序后的数组
[0, 3, 5, 6, 7]

整合代码

package com.nanzx.sort;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int arr[] = { 6, 3, 5, 7, 0 };
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		bubbleSort(arr);
		System.out.println("排序后");
		System.out.println(Arrays.toString(arr));
	}

	public static void bubbleSort(int[] arr) {
		for (int n = 1; n < arr.length; n++) {
			int temp;
			for (int i = 0; i < arr.length - n; i++) {
				if (arr[i] > arr[i + 1]) {
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
		}
	}
}

优化

如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。

package com.nanzx.sort;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int arr[] = { 6, 3, 5, 7, 0 };
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		bubbleSort(arr);
		System.out.println("排序后");
		System.out.println(Arrays.toString(arr));
	}

	public static void bubbleSort(int[] arr) {
		boolean flag = false;
		for (int n = 1; n < arr.length; n++) {
			int temp;
			for (int i = 0; i < arr.length - n; i++) {
				if (arr[i] > arr[i + 1]) {
					flag = true;
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
			if (!flag) {
				break;
			} else {
				flag = false;
			}
		}
	}
}

测试冒泡排序的速度O(n²)

package com.nanzx.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class BubbleSort {

	public static void main(String[] args) {

		// 测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
		// 创建一个80000个元素的随机的数组
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);

		// 测试冒泡排序
		bubbleSort(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是=" + date2Str);
	}

	public static void bubbleSort(int[] arr) {
		boolean flag = false;
		for (int n = 1; n < arr.length; n++) {
			int temp;
			for (int i = 0; i < arr.length - n; i++) {
				if (arr[i] > arr[i + 1]) {
					flag = true;
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
				}
			}
			if (!flag) {
				break;
			} else {
				flag = false;
			}
		}
	}
}