数据结构与算法系列——排序(8.1)_冒泡排序

曾经终败给现在 2021-10-29 16:06 348阅读 0赞

# 1. 工作原理（定义） #

核心思想：冒泡排序是一种典型的 *交换排序* ，通过比较相邻元素大小来决定是否交换位置

冒泡排序的思想：不停地比较相邻的两个记录，如果相邻的两个记录的次序是反序则交换，直到所有的记录都已经排好序了（使关键字最小或最大的记录如气泡一般逐渐往上“漂浮”直至“水面”，所以叫冒泡排序）。

# 2. 算法步骤 #

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

![728328-20190510113910412-697912233.png][]

# 3. 动画演示 #

![bubbleSort.gif][]

# 4. 性能分析 #

## 1. 时间复杂度 ##

（1）顺序排列时，冒泡排序总的比较次数为n-1（比较一轮后就跳出循环），移动次数为0；   
　　（2）逆序排序时，冒泡排序总的比较次数为n(n-1)/2，移动次数为n(n-1)/2次；   
　　（3）当原始序列杂乱无序时，平均时间复杂度为O(n^2)。

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数  ![b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg][] 和记录移动次数  ![48540923dd54564e27333d86b1de9c82d1584f3f.jpg][] 均达到最小值：  ![8326cffc1e178a8244f3b2bafb03738da877e8da.jpg][] ，  ![b21c8701a18b87d6007472a0050828381f30fd5f.jpg][] 。所以，冒泡排序最好的时间复杂度为  ![b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg][] 。

*　　若初始文件是反序的，需要进行 ![8b82b9014a90f60364df45f83b12b31bb051ed26.jpg][] 趟排序。每趟排序要进行 ![503d269759ee3d6d1214597441166d224e4adebb.jpg][] 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：* * 。冒泡排序的最坏时间复杂度为 ![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][] 。综上，因此冒泡排序总的平均时间复杂度为 ![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][] 。*

## 2. 空间复杂度 ##

冒泡排序排序过程中，Swap函数需要一个临时变量temp进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。

## 3. 算法稳定性  ##

冒泡排序在排序过程中，元素两两交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

## 4. 初始顺序状态 ##

1.  比较次数：
2.  移动次数：
3.  复杂度：    
4.  排序趟数：

## 5. 归位 ##

能归位，每一趟排序有一个元素归位。

## 6. 优点 ##

# 6. 改进算法 #

1.  对于是否已经是有序排列进行判断；
2.  对已经排序好的元素不参与重复的比较。

# 7. 具体代码 #

public int[] bubbleSort1(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { //等于就不交换，保证了稳定性 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return arr; } /* *设置一个标识，如果在某一趟遍历中没有发生交换，说明排序已经完成，即算法完成 */
    public int[] bubbleSort2(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flagChange = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flagChange = false; } } if (flagChange) { break; } } return arr; } // set flag to indicate what next step should begin from
    public int[] bubbleSort3(int[] sourceArray) { // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); int tmpNextPosition = sourceArray.length-1; for (int i = 1; i < arr.length; i++) { // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flagChange = true; int nextPosition = tmpNextPosition; for (int j = 0; j < nextPosition; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flagChange = false; tmpNextPosition = j; } } if (flagChange) { break; } } return arr; }

# 8. 参考网址 #

1.  [数据结构基础学习笔记目录][Link 1]
2.  [75-交换排序——冒泡排序][75-]
3.  [排序算法系列之冒泡排序][Link 2]
4.  [https://visualgo.net/en/sorting][https_visualgo.net_en_sorting]
5.  [https://www.runoob.com/w3cnote/bubble-sort.html][https_www.runoob.com_w3cnote_bubble-sort.html]
6.  [https://github.com/hustcc/JS-Sorting-Algorithm][https_github.com_hustcc_JS-Sorting-Algorithm]
7.  [冒泡排序][Link 3]

转载于:https://www.cnblogs.com/haimishasha/p/10843628.html

[728328-20190510113910412-697912233.png]: /images/20211029/32c3e64c709f4d5b83af9ca7a6c4bc4b.png
[bubbleSort.gif]: /images/20211029/c61f70e67a0a459e9efd4cc1f2de4873.png
[b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D12/sign=5e6ca6622c738bd4c021b633a08bb91b/b3b7d0a20cf431ad4f379a864936acaf2fdd98ac.jpg
[48540923dd54564e27333d86b1de9c82d1584f3f.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=c765e07cd5ca7bcb797bc329bf09e8ac/48540923dd54564e27333d86b1de9c82d1584f3f.jpg
[8326cffc1e178a8244f3b2bafb03738da877e8da.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D84/sign=2cfb4bf49182d158bf8254b5810a024c/8326cffc1e178a8244f3b2bafb03738da877e8da.jpg
[b21c8701a18b87d6007472a0050828381f30fd5f.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D66/sign=1745c99097cad1c8d4bbff217e3e11cd/b21c8701a18b87d6007472a0050828381f30fd5f.jpg
[b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D33/sign=feddd1e257fbb2fb302b5e114e4a94f7/b58f8c5494eef01f9d1ac17ae2fe9925bc317d07.jpg
[8b82b9014a90f60364df45f83b12b31bb051ed26.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D32/sign=411c7ed7d309b3deefbfe26acdbf0492/8b82b9014a90f60364df45f83b12b31bb051ed26.jpg
[503d269759ee3d6d1214597441166d224e4adebb.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D30/sign=3af139940cf41bd5de53eef450da752f/503d269759ee3d6d1214597441166d224e4adebb.jpg
[e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D40/sign=17b28fa860d0f703e2b294dc09fa9d5c/e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg
[Link 1]: https://blog.csdn.net/qq_35733751/article/details/80453428
[75-]: https://blog.csdn.net/qq_35733751/article/details/81905461
[Link 2]: https://blog.csdn.net/hlc246/article/details/81011753
[https_visualgo.net_en_sorting]: https://visualgo.net/en/sorting
[https_www.runoob.com_w3cnote_bubble-sort.html]: https://www.runoob.com/w3cnote/bubble-sort.html
[https_github.com_hustcc_JS-Sorting-Algorithm]: https://github.com/hustcc/JS-Sorting-Algorithm
[Link 3]: https://blog.csdn.net/liudongdong19/article/details/82906953