冒泡排序详解_超详细电音

大家好，又见面了，我是你们的朋友全栈君。

1、什么是冒泡排序？

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

冒泡排序的原理： 每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。 而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

2、冒泡排序到底是如何排序的呢？

下面通过一个动图来看一看冒泡排序到底是怎么样移动的

在这里插入图片描述

具体是如何移动的呢？这里参考了(帅地的冒泡排序)

（1）起始时，左下标指向第一个石子，右下标指向第二个石子，然后比较

在这里插入图片描述

（2）然后左右下标同时向右移动，再次比较

在这里插入图片描述

（3）第一趟结束之后，最大的石子就移动到了最右边

在这里插入图片描述

（4）接下来就从剩下 3 个没排好序的石子中继续选出最大的，规则和上面一样

在这里插入图片描述

（5）下面给出这 4 个石子完整的演示过程

在这里插入图片描述

3、时间复杂度

由上图可知，4 个石子的时候排完序需要 3 趟，第一趟需要比较3次，第二趟需要比较2次，第三趟需要比较1次，那一共比较了 3 + 2 + 1 次；

那如果有 n 个石子呢？

那就需要 (n-1) + (n-2) +…+2+1 次，这不就是一个等差数列吗，很显然：

在这里插入图片描述

根据复杂度的规则，去掉低阶项（也就是 n/2）,并去掉常数系数，那复杂度就是 **O(n^2)**了； 冒泡排序也是一种稳定排序，因为在两个数交换的时候，如果两个数相同，那么它们并不会因为算法中哪条语句相互交换位置。

4、冒泡排序代码原始版

//按照刚才那个动图进行对应
//冒泡排序两两比较的元素是没有被排序过的元素--->
public void bubbleSort(int[] array){ 

for(int i=0;i<array.length-1;i++){ 
//控制比较轮次，一共 n-1 趟
for(int j=0;j<array.length-1-i;j++){ 
//控制两个挨着的元素进行比较
if(array[j] > array[j+1]){ 

int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}

疑问环节

小花：第一层循环是用来控制趟数，也就是 n 个数就要比较 n-1 趟；那么第二层循环能不能具体解答一下呢？ 小明：第二层是控制第 i+1 趟（因为循环中 i 是从 0 开始的）的比较次数，那么 i+1 趟就是比较了 N-1-i 次 小花：还是不是很清楚，能不能用图形来跟我描述一下呀？ 小明：当然可以呢，下面通过几张图来给你讲解一下。

在这里插入图片描述

在这里插入图片描述

小花：这个明白了，但是如果遇到下面这种情况呢？也就是执行到最后三轮的时候，发现整个数列已经是有序的了，可以按上面的代码执行的话算法还是仍然“兢兢业业”地继续执行第七轮、第八轮。这个可不可以优化一下呢？ 小明：当然可以优化，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。 小花：那到底又怎么样优化上面的代码才能得到这种效果呢？ 小明：其实也很简单，就是将上面代码做一点点小小改动即可，也就是利用布尔变量 isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

5、冒泡排序代码优化版

public static int[] bubbleSort(int[] arr) { 

if (arr == null || arr.length < 2) { 

return arr;
}
for (int i = 0; i < arr.length - 1; i++) { 

boolean isSorted  = true;//有序标记，每一轮的初始是true
for (int j = 0; j < arr.length -i - 1; j++) { 

if (arr[j + 1] < arr[j]) { 

isSorted  = false;//有元素交换，所以不是有序，标记变为false
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
//一趟下来是否发生位置交换，如果没有交换直接跳出大循环
if(isSorted )
break;
}
return arr;
}

小花：懂了，我还有一个问题。那如果数列中前半部分是无序的，后半部分是有序的呢？比如（3，4，2，1，5，6，7，8）这个数组，其实后面的许多元素已经是有序的了，但是每一轮还是白白比较了许多次呢？例如：

第一轮：

在这里插入图片描述

元素 3 和元素 4 比较，3 大于 4，所以位置不变

接着元素 4 和元素 2 比较，4 大于 2，所以 4 和 2 交换

在这里插入图片描述

接着元素 4 和元素 1 交换

在这里插入图片描述

再接着就发现后面其实就是有序数列了，但是还是要每一次两两相比，这样就白白比较了很多次了

在这里插入图片描述

第二轮：

在这里插入图片描述

元素 3 和元素 2 比较，3 大于 2，所以 3 和 2 交换

在这里插入图片描述

元素 3 和 1 比较，发现 3 大于 1，所以 3 和 1 交换

在这里插入图片描述

再接着就发现后面其实又是有序数列了，但是还是要每一次两两相比，这样也白白比较了很多次了

在这里插入图片描述

小明：对于上面你提出的问题，关键在于对这数列有序区的界定。如果按冒泡排序代码原始版来分析的话，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ……。 但是呢，实际数列真正的有序区可能会大于这个长度，也就是你上面这个例子，第二轮中后面 5 个实际上都已经属于有序区了。因此后面的比较是没有意义的了。 我们可以这样做来避免这种情况：在每一轮排序的最后，记录一下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

6、冒泡排序代码升级版

public static int[] bubbleSort(int[] arr) { 

if (arr == null || arr.length < 2) { 

return arr;
}
//记录最后一次交换的位置
int lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要比到这里为止
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) { 

boolean isSorted  = true;//有序标记，每一轮的初始是true
for (int j = 0; j < sortBorder; j++) { 

if (arr[j + 1] < arr[j]) { 

isSorted  = false;//有元素交换，所以不是有序，标记变为false
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex
//一趟下来是否发生位置交换，如果没有交换直接跳出大循环
if(isSorted )
break;
}
return arr;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/180211.html原文链接：https://javaforall.cn