- 时间复杂度：高效的排序算法，比较次数和移动次数都应该尽可能的少。
- 空间复杂度：算法执行期所需要辅助空间和待排序的数据量无关。理想空间复杂度为O(1)
简述
冒泡排序就如同水中的水泡往水面上浮过程一样，越来越大。冒泡排序是最简单的交换排序，通过两两相邻比较，如果发生逆序则进行交换，如此循环，直至全部排序成功
算法思想
- 设定排序数组为r[0··n-1]中，一共n个待排序数。第一躺排序：首先将r[0]与r[1]进行比较，若逆序，则交换r[0]与r[1]，然后将r[1]与r[2]进行比较，逆序则交换，一次类推，直到r[n-2]与r[n-1]比较判断后，第一趟排序结束，最后一个数字则最终排序的最后一位值。
- 第二趟排序，则是将r[0]到r[n-1]，第一步方法进行排序，得到最终排序的r[n-2]位值。
- 重复上述比较过程，知道某一趟，没有进行交换为止，说明已经排序结束。
算法实现
public void sort() {
//待排序数组
int[] ints = new int[]{1, 33, 44, 55, 6, 2, 3, 22, 77, 88, 123, 54};
//从小到大
//最大比较n-1趟
for (int i = 1; i <= ints.length; i++) {
System.out.println("第" + i + "趟排序");
boolean hasChange = false;
//每一趟比较0到j
for (int j = 0; j < ints.length - i; j++) {
if (ints[j] >= ints[j + 1]) {
int temp = ints[j];
ints[j] = ints[j + 1];
ints[j + 1] = temp;
hasChange = true;
}
}
if (!hasChange) {
System.out.println("没有交换，排序完成");
break;
}
}
for (int intTemp : ints) {
System.out.print(intTemp + " ");
}
}
算法实现一般是两重循环，外层是控制躺数，内层控制比较数。具体如何控制可根据自己的想法去实现。
算法分析
- 时间复杂度
- 最好的情况：初始的时候就排序好了，只需要进行一趟比较，且不移动记录
- 最坏的情况：需要进行n-1趟排序，那么总的关键字比较次数：第一趟n-1次，第二趟n-2次，第三趟n-3次，所以总的为n(n-1)/2约等于n2/2。总的移动次数(假定每次交换都移动3次记录)，3n(n-1)/2约等于3n2/2。
所以，最好和最坏平均一下，那么平均情况下，冒泡排序记录移动次数为n2/4和3n2/4。时间复杂度为O(n2)
- 空间复杂度
- 由于交换的时候，辅助空间只需要一个来做暂时存储，所以空间复杂度为O(1)
算法特点
- 是稳定排序
- 由于是相邻比较，所以可用于链式存储结构
- 移动次数比较多，算法平均性能比直接插入排序差。当初始记录无序，n较大的时候不适用了
冒泡可以说是最基本的排序手法之一。这个手法想必是各种语言学习的时候都有所使用的，对咱们排序思想有启发作用。
