admin 管理员组文章数量: 1086927
数据结构之冒泡排序算法（图解+分析+代码调优）
文章目录
- 一、冒泡排序的介绍
- 二、图示冒泡排序全过程
- 三、冒泡排序图示小结
- 四、Java代码实现冒泡排序（优化前）
- 五、优化方法
- 六、Java代码实现冒泡排序（优化后）
- 七、测试冒泡排序是否正确
- 八、使用大量数据测试冒泡排序的时间
- 九、时间复杂度
- 十、空间复杂度
- 十一、稳定性
- 十二、全部代码
一、冒泡排序的介绍
冒泡排序是一种比较简单的排序算法，其基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，可以形象的理解为像水底下的气泡一样逐渐向上冒，较大的数字沉底，较小的数字上浮。
二、图示冒泡排序全过程
三、冒泡排序图示小结
（1）一共进行数组的大小-1次排序（也就是循环多少次）
（2）每一趟排序的次数逐渐减少，已沉底的元素不再比较（需要两层循环）
（3）如果在某一次排序中，一次交换都没有发生，则可以退出提前结束排序（可以优化）
四、Java代码实现冒泡排序（优化前）
public static void bubbleSort(int[] arr) {// 每一趟排序，就是将最大的排序在最后int temp = 0; //临时变量for (int i = 0; i < arr.length - 1; i++) { // 外循环，一共循环数组长度-1次for (int j = 0; j < arr.length - 1 - i; j++) { // 内循环，每次只需要排序沉底元素之前的元素// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
五、优化方法
因为在排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明数组有序，因此定义一个boolean标识位，如果发生交换则置为true，如果一次交换都没有，则退出排序过程，从而减少不必要的排序，实现优化
六、Java代码实现冒泡排序（优化后）
public static void bubbleSort(int[] arr) {// 每一趟排序，就是将最大的排序在最后int temp = 0; //临时变量boolean flag = false; // 标识变量，表示是否进行过交换for (int i = 0; i < arr.length - 1; i++) { // 外循环，一共循环数组长度-1次for (int j = 0; j < arr.length - 1 - i; j++) { // 内循环，每次只需要排序沉底元素之前的元素// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag) { // 在一趟排序中，一次交换都没有发生过break;} else {flag = false; // 重置flag，进行下次判断}}}
七、测试冒泡排序是否正确
public class BubbleSort {public static void main(String[] args) {// 测试冒泡排序int[] arr = {20, 9, -1, 10, 3};System.out.println("排序前");System.out.println(Arrays.toString(arr));bubbleSort(arr);System.out.println("排序后");System.out.println(Arrays.toString(arr));}
}// 输出结果
排序前
[20, 9, -1, 10, 3]
排序后
[-1, 3, 9, 10, 20]
由结果可知，算法正确
八、使用大量数据测试冒泡排序的时间
这里我使用80000条随机数据，测试冒泡排序算法的排序时间：
public class BubbleSort {public static void main(String[] args) {// 测试冒泡排序int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {// 会生成[0,8000000)的数arr[i] = (int)(Math.random() * 8000000); }Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String datestr1 = simpleDateFormat.format(date1);System.out.println("排序前的时间是:"+datestr1);// 调用冒泡排序方法bubbleSort(arr);Date date2 = new Date();String datestr2 = simpleDateFormat.format(date2);System.out.println("排序前的时间是:"+datestr2);}
测试时间结果如下：
排序前的时间是:2020-02-24 19:54:19
排序前的时间是:2020-02-24 19:54:28
8万条随机数据大约用时9秒，还是比较慢，后面我会带来更快的排序算法讲解
九、时间复杂度
优化前：
- 最优的时间复杂度：O(n^2) --------------------------> 此种情况下在排序的开始已经排好序
- 最坏的时间复杂度：O(n^2) --------------------------> 此种情况下在排序的开始为逆序
- 平均的时间复杂度：O(n^2)
优化后：
- 时间复杂度：O(n)
十、空间复杂度
- 最优的空间复杂度：0 --------------------------> 此种情况下在排序的开始已经排好序
- 最坏的空间复杂度：O(n) --------------------------> 此种情况下在排序的开始为逆序
- 平均的空间复杂度：O(1)
十一、稳定性
冒泡排序是一种稳定的排序算法
十二、全部代码
package Sort;import java.text.SimpleDateFormat;
import java.util.Date;public class BubbleSort {public static void main(String[] args) {// 测试冒泡排序int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int)(Math.random() * 8000000); // 会生成[0,8000000)的数}Date date1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String datestr1 = simpleDateFormat.format(date1);System.out.println("排序前的时间是:"+datestr1);// int[] arr = {20, 9, -1, 10, 3};
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));bubbleSort(arr);
// System.out.println("排序后");
// System.out.println(Arrays.toString(arr));Date date2 = new Date();String datestr2 = simpleDateFormat.format(date2);System.out.println("排序前的时间是:"+datestr2);}// 将前面的冒泡排序算法，封装成一个方法public static void bubbleSort(int[] arr) {// 每趟排序，就是将最大的排序在最后int temp = 0; //临时变量boolean flag = false; // 标识变量，表示是否进行过交换for (int i = 0; i < arr.length - 1; i++) { // 外循环，一共循环数组长度-1次for (int j = 0; j < arr.length - 1 - i; j++) { // 内循环，每次只需要排序沉底元素之前的元素// 如果前面的数比后面的数大，则交换if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag) { // 在一趟排序中，一次交换都没有发生过break;} else {flag = false; // 重置flag，进行下次判断}}}}
本文标签： 数据结构之冒泡排序算法（图解分析代码调优）
版权声明：本文标题：数据结构之冒泡排序算法（图解+分析+代码调优） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687296228a86360.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论