Java 算法之冒泡排序
算法介绍
冒泡排序又称起泡排序。它是通过一系列的“交换”动作完成的。首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换······一直按这种方式进行下去，最终最大的那个关键字被交换到了最后，一趟冒泡排序完成。经过多趟这样的排序，最终使整个序列有序。这个过程中，大的关键字像石头一样“沉底”，小的关键字像气泡一样逐渐向上“浮动”，冒泡排序的名字由此而来。要注意的是，冒泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。
冒泡排序算法常规代码：
public static void bubbleSort(int R[], int n){ //默认待排序关键字为整型
int i, j, flag;
int temp;
for(i = n - 1; i >= 1; --i){
flag = 0; //变量 flag 用来标记本趟排序是否发生了交换
for(j = 1; j <= i; ++j){
if(R[j-1] > R[j]){
temp = R[j];
R[j] = R[j-1];
R[j-1] = temp;
flag = 1; //如果没发生交换，则flag的值为0；
} //如果发生了交换，则flag的值改为1
}
if(flag == 0) //一趟排序过程中没有发生关键字交换，则证明序列有序
return; //排序结束
}
}
冒泡排序算法速记代码：
public static void bubbleSort(int[] arr){
for(int x = 0; x < arr.length - 1; x++){
for(int y = 0; y < arr.length - x - 1; y++){
if(arr[y] > arr[y+1]){
int temp = arr[y];
arr[y] = arr[y+1];
arr[y+1] = temp;
}
}
}
}
冒泡排序算法常规代码性能分析：
-
时间复杂度分析
由冒泡排序算法代码可知，可选取最内层循环中的关键字交换操作作为基本操作。
1) 最坏情况，待排序列逆序，此时对于外层循环的每次执行，内层循环中 if 语句的条件 R[j] < R[j-1] 始终成立，即基本操作执行的次数为 n - i。i 的取值为 1 ~ n - 1。因此，基本操作总的执行次数为 (n - 1 + 1)(n - 1) / 2 = n(n - 1) / 2，由此可知时间复杂度为 O(n²)。
2) 最好情况，待排序列有序，此时内层循环中 if 语句的条件始终不成立，交换不发生，且内层循环执行 n - 1 次后整个算法结束，可见时间复杂度为 O(n)。
综合以上两种情况，平均情况下的时间复杂度为 O(n²)。
-
空间复杂度分析
由算法代码可以看出，额外辅助空间只有一个 temp，因此空间复杂度为 O(1)。
