普通的冒泡排序相信大家信手拈来，不在赘述！
第一版
public class BubbleSort {
public static void main(String[] args) {
int[] ARRAY = {5，8，6，3，9，2，1，7};
sort(ARRAY);
System.out.println(Arrays.toString(ARRAY));
}
public static void sort(int[] array) {
int temp=0; //临时变量
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length - 1 -i; j++) { //比较的次数
if (array[j + 1] < array[j]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
}
时间复杂度 对于上面12个数据项，从第一个元素开始，第一趟比较了11次，第二趟比较了10次，依次类推，一直到最后一趟，就是：
11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66次 若有n个元素，则第一趟比较为(n-1)次，第二趟比较为(n-2)次，依次类推：
(n-1) + (n-2) + (n-3) + …+ 2 + 1 = n * (n-1)/2 在大O表示法中，去掉常数系数和低阶项，该排序方式的时间复杂度为：O(n2)
算法稳定性 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。——百度百科
在代码中可以看到，array[j + 1] = array[j]的时候，我们可以不移动array[i]和array[j]，所以冒泡排序是稳定的。
第二版
原始的冒泡排序有哪些优化点呢？
让我们回顾一下刚才描述的排序细节，仍然以5，8，6，3，9，2，1，7这个数列为例，当排序算法分别执行到第六、第七、第八轮的时候，
很明显可以看出，自从经过第六轮排序，整个数列已然是有序的了。可是我们的排序算法仍然“兢兢业业”地继续执行第七轮、第八轮。
这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。
public class BubbleSort {
public static void main(String[] args) {
int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
sort(ARRAY);
System.out.println(Arrays.toString(ARRAY));
}
public static void sort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean flag=false;//标识变量，是否进行过交换
for (int j = 0; j < array.length - 1 -i; j++) {
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
//有元素交换，所以不是有序，标记变为false
flag=true;
}
}
if (!flag) break;
//System.out.println(Arrays.toString(array));//作为展示用,看看打印了几轮
}
}
}
这一版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
第三版
这个数列的特点是前半部分（3，4，2，1）无序，后半部分（5，6，7，8）升序，并且后半部分的元素已经是数列最大值。
按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ……
实际上，数列真正的有序区可能会大于这个长度，比如例子中仅仅第二轮，后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。
如何避免这种情况呢？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。
//优化 -有序区========================================================
public class BubbleSort {
public static void main(String[] args) {
int[] ARRAY = {24, 7, 43, 78, 62, 8, 8, 18, 54, 79, 173, 239};
sort(ARRAY);
System.out.println(Arrays.toString(ARRAY));
}
public static void sort(int[] array) {
//记录最后一次交换的位置
int lastExchangeIndex=0;
//无序数列的边界，每次只要比到这里即可
int sortBorder=array.length-1;
for (int i = 0; i < array.length-1; i++) {
boolean flag=false;//标识变量，是否进行过交换
for (int j = 0; j < sortBorder; j++) {
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
//有元素交换，所以不是有序，标记变为false
flag=true;
//把无序数列的边界更新为最后一次交换元素的位置
lastExchangeIndex=j;
}
}
sortBorder=lastExchangeIndex;
if (!flag) break;
System.out.println("第"+(i+1)+"次："+Arrays.toString(array));//作为展示用
}
}
}
第四版
冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。算法的每一轮从都是从左到右比较元素，进行单向的位置交换。
那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是双向的。
鸡尾酒（双向冒泡）排序算法基本过程
（1）先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端；
（2）再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端；
以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束.
排序过程就像钟摆一样，第一轮从左到右，第二轮从右到左，第三轮再从左到右……
//冒泡之鸡尾酒排序=====================================================
public class BubbleSort {
public static void main(String[] args) {
int[] ARRAY = {2,3,4,5,6,7,8,1};
sort(ARRAY);
System.out.println(Arrays.toString(ARRAY));
}
public static void sort(int[] array) {
int temp=0;
for (int i = 0; i < array.length/2; i++) {
boolean flag=false;//标识变量，是否进行过交换
//奇数轮，从左向右比较和交换
for (int j = i; j < array.length-1-i; j++) {
if (array[j + 1] < array[j]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
//有元素交换，所以不是有序，标记变为false
flag=true;
//把无序数列的边界更新为最后一次交换元素的位置
}
}
System.out.println("第"+(i+1)+"次："+Arrays.toString(array));//作为展示用 避坑 不要写成i++
if (!flag) break;
//偶数轮之前，重新标记为false
flag=false;
//偶数轮 从右向左比较和交换
for (int j = array.length-1-i; j > i; j--) {
if(array[j]<array[j-1]){
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
//有元素交换，不是有序，flag设置为true
flag=true;
}
}
System.out.println("第"+(i+1)+"次："+Arrays.toString(array));//作为展示用
if (!flag) break;
}
}
}
最后，附上下图：
- 打赏
- 微信
- 支付宝
