一、算法原理
冒泡算法的原理非常简单:首先将要排序的数列分成两部分,已排序的部分和未排序的部分。每一轮排序中,从第一个元素开始,依次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换两个元素的位置,直到整个数列都排好序为止。
假设要排序的数列为A[],其长度为n。则第一轮排序时需要比较n-1次,第二轮排序时需要比较n-2次,以此类推,第k轮排序时需要比较n-k次。因此,总共需要进行n(n-1)/2次比较,时间复杂度为O(n^2)。
二、算法流程
具体来说,冒泡算法的流程如下:
1、首先,将要排序的数列A[]作为输入,其长度为n;
2、然后,从第一个元素开始,依次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换两个元素的位置;
3、接着,将指针向后移动一位,继续比较相邻的两个元素,并进行交换,直到整个数列都排好序为止;
4、最后,输出已排序的数列A[]。
三、优化算法
冒泡排序的时间复杂度为O(n^2),当数据量较大时,会出现比较耗费时间的情况。因此,我们可以进行一些优化,使得算法的效率更高。
1、当在某一轮排序中,没有任何一次交换操作发生时,表示数列已经有序,此时可以直接退出循环。
2、在排序过程中,记录最后一次发生交换的位置,之后的数列都已排好序,因此可以减少比较次数:
public class BubbleSortAnimation {
public static void main(String[] args) {
int[] arr = {10, 2, 1, 42, 22, 8, 9, 11, 1, 4, 6, 33, 20, 11, 17, 55, 24};
int n = arr.length;
int lastExchange = 0; // 最后一次交换位置
int sortBorder = n - 1; // 无序数列的边界
for (int i = 0; i < n - 1; i++) {
boolean flag = true; // 标记是否发生交换
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false; // 发生交换
lastExchange = j; // 记录最后一次交换位置
}
}
// 打印每一轮排序后的数组情况
System.out.print("第 " + (i + 1) + " 轮排序后的数组为:");
for (int k = 0; k < n; k++) {
System.out.print(arr[k] + " ");
}
System.out.println();
sortBorder = lastExchange; // 更新无序数列的边界
if (flag) {
break; // 本轮排序未发生交换,说明已有序
}
}
}
}
示例代码的输出日志:
第 1 轮排序后的数组为:2 1 10 22 8 9 11 1 4 6 33 20 11 17 42 24 55
第 2 轮排序后的数组为:1 2 10 8 9 11 1 4 6 22 20 11 17 33 24 42 55
第 3 轮排序后的数组为:1 2 8 9 10 1 4 6 11 20 11 17 22 24 33 42 55
第 4 轮排序后的数组为:1 2 8 9 1 4 6 10 11 11 17 20 22 24 33 42 55
第 5 轮排序后的数组为:1 2 8 1 4 6 9 10 11 11 17 20 22 24 33 42 55
第 6 轮排序后的数组为:1 2 1 4 6 8 9 10 11 11 17 20 22 24 33 42 55
第 7 轮排序后的数组为:1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55
第 8 轮排序后的数组为:1 1 2 4 6 8 9 10 11 11 17 20 22 24 33 42 55
动图效果:
四、算法分析
1、时间复杂度:最好情况下为O(n),即数列已经排序完成,无需进行任何比较操作;最坏情况下为O(n^2);平均情况下为O(n^2)。
2、空间复杂度:由于只需要一个额外的变量来保存临时变量,并没有使用任何额外的空间,空间复杂度为O(1)。
3、稳定性:冒泡排序是一种稳定排序算法,因为在比较相邻的两个元素时,只有在前一个元素大于后一个元素时才会进行交换,不会改变相同元素之间的顺序。
五、总结
冒泡排序是一种简单而又经典的排序算法,虽然其时间复杂度较高,但由于其实现简单,易于理解,是许多排序算法中最为基础的一种。在实际应用中,我们可以根据具体情况对其进行优化,从而提高算法的效率。