一、算法实现
- 基本实现
/**
* 冒泡排序（交换排序）
*/
public static int[] sortBubble(int[] arr) {
int i, j, temp;
for (i = 0; i < arr.length - 1; i++) {
for (j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
- 算法改进
设置标志变量：标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换，说明序列已经有序了，不必继续进行下去了。
/**
* 设置标志变量
*/
public static int[] sortBubble(int[] arr) {
int i, j, temp, change = 1;
for (i = 0; i < arr.length - 1 && change != 0; i++) {
change = 0;
for (j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
change = 1;
}
}
}
return arr;
}
二、运行示例
{20, 15, 10, 12}
【15, 20】, 10, 12 //--> [0]与[1]比较，大的放后面
15, 【10, 20】, 12 //--> [1]与[2]比较，大的放后面
15, 10, 【12, 20】 //--> [2]与[3]比较，大的放后面
（第一个内循环后最大的数在最后的位置）
【10, 15】, 12, 20 //--> [0]与[1]比较，大的放后面
10, 【12, 15】, 20 //--> [1]与[2]比较，大的放后面
（第二个内循环后第二大的数在倒数第二的位置）
三、性能分析
- 时间复杂度
在设置标志变量之后：
1.当原始序列“正序”排列时，冒泡排序总的比较次数为n-1，移动次数为0，也就是说冒泡排序在最好情况下的时间复杂度为O(n)
2.当原始序列“逆序”排序时，冒泡排序总的比较次数为n(n-1)/2，移动次数为3n(n-1)/2次，所以冒泡排序在最坏情况下的时间复杂度为O(n^2)
3.当原始序列杂乱无序时，冒泡排序的平均时间复杂度为O(n^2)
- 空间复杂度
冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。
- 稳定性
冒泡排序在排序过程中，元素两两交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
