Java排序算法之冒泡排序（java冒泡排序和快速排序）

今天我们来了解下冒泡的的Java实现，我们从这几个方面入手：

• 原理介绍及时间复杂度
• Java代码实现
• 优化思考

一 、原理介绍

原理：每次比较两个相邻的元素，将值大的元素交换至右端，类似于一个气泡，不断的移动。

时间复杂度：O(n*n)

二、Java代码实现

package com.example.demo.dataStructure.sort;
/**
 * 冒泡排序-常规写法
 */
public class BubbleSort {
	public static void bubbleSort(int[] arg) {
		for (int i = 0; i < arg.length; i++) {
			for (int j = 0; j < arg.length - i - 1; j++) {
				if (arg[j] > arg[j + 1]) {
					int temp = arg[j];
					arg[j] = arg[j + 1];
					arg[j + 1] = temp;
				}
			}
		}
	}
	public static void main(String[] args) {
		int[] arg = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		bubbleSort(arg);
		for (int i = 0; i < arg.length; i++) {
			System.out.print(arg[i]);
		}
	}
}

运行结果如下：

123456789

三、优化思考

上面我们给出的数组是一个逆序，那如果我们给出的数组是一个顺序呢，即本来就是有顺序的，是不是也要每次都遍历这么多下呢？再或者我们给出的是一个部分有序的数组呢？

我们先优化外层循环：

// 优化外层循环
public static void bubbleSort2(int[] arg) {
	for (int i = 0; i < arg.length;i++) {
		boolean isSorted = true; // 增加一个标志位，每趟都初始化
		for (int j = 0; j < arg.length - i - 1; j++) {
			if (arg[j] > arg[j + 1]) {
				int temp = arg[j];
				arg[j] = arg[j + 1];
				arg[j + 1] = temp;
				isSorted = false; // 若有交换，则更改标志
			}
		}
		if (isSorted) { // 根据标志判断是否有交换
			break;
		}
	}
}

我们还可以优化内层循环：

// 优化内层循环
public static void bubbleSort3(int[] arg) {
	int k = arg.length, pos = 0; // 初始化内层循环的次数，临时位置变量
	for (int i = 0; i < arg.length;i++) {
		boolean isSorted = true;
		for (int j = 0; j < k - i - 1; j++) {
			if (arg[j] > arg[j + 1]) {
				int temp = arg[j];
				arg[j] = arg[j + 1];
				arg[j + 1] = temp;
				isSorted = false;
				pos = j; // 每趟比较中，若有交换，记录下位置
			}
		}
		k = pos; // 将位置赋给内层循环的次数
		if (isSorted) {
		break;
		}
	}
}