概述
冒泡排序是一种简单的排序算法. 它重复的走过要排序的数列, 每次比较相邻的两个元素, 若它们的顺序错误就把他们进行交换, 如此循环进行, 直到冒泡到最后一个元素或本次比较不需要进行冒泡 就结束.
因为元素就像一个一个向上冒, 故而叫做冒泡算法, 个人理解.
冒泡排序的执行步骤如下(从小到大):
- 从第一个元素开始, 向后依次比较 相邻元素的大小. 若前一个大, 则交换
- 做到最后一位时, 最后的元素是最大的数
- 最后一个元素已经比较完毕, 将其从比较序列中排除, 重复以上步骤.
- 重复以上步骤, 知道没有元素需要交换或冒泡完毕
其时间空间复杂度如下:
不难理解, 直接上代码了.
Java代码实现
/**
* 冒泡排序实现数组排序, 从小到达顺序
*
* @param arr
*/
public static void bubbleSort(int[] arr) {
/*
* 1. 遍历数组, 将左侧>右侧的元素交换
* 2. 此时最大元素冒泡到数组末尾
* 3. 将已经排序的元素去除, 重复步骤1-2
*/
// i从后向前, 即将最大的冒泡到最后, 则不再理会这一元素
for (int i = arr.length; i > 0; i--) {
// 标志位, 判断是否进行了冒泡操作
boolean flag = false;
// 用于冒泡循环
for (int j = 0; j < i - 1; j++) {
// 若左侧元素大, 则进行交换
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
// 若没有进行冒泡操作, 表示已经排序完成, 退出
if (!flag) {
break;
}
}
}