数据结构和算法学习--冒泡排序

Leefs 2020-02-01 PM 1871℃ 0条

# 数据结构和算法学习--冒泡排序

### 一、基本介绍

冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

**优化：**

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

### 二、演示冒泡排序过程

![14.冒泡排序算法01.png][1]

**冒泡排序规则**

（1）一共进行数组的大小-1次大的循环

（2）每一趟排序的次数在逐渐的减少

（3）如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序

示例：

```
将五个无序的数：3,9,-1,10,-2使用冒泡排序法将其排成一个从小到大的有序数列。
```

未优化代码

```java
//3,9,-1,10,-2使用冒泡排序法将其排成一个从小到大的有序数列
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        int temp;
        for(int i=0;i<arr.length-1;i++){
            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;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
```

> 运行结果

```
[-2, -1, 3, 9, 10]
```

优化后代码

```java
//3,9,-1,10,-2使用冒泡排序法将其排成一个从小到大的有序数列
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        int temp=0;
        boolean flag=false;
        for(int i=0;i<arr.length-1;i++){
            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;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
```

> 运行结果

```
[-2, -1, 3, 9, 10]
```

完整代码

```java
public class BubbleSort2{

public static void main(String[] args) {
//		int arr[] = {3, 9, -1, 10, 20};
//
//		System.out.println("排序前");
//		System.out.println(Arrays.toString(arr));

//为了容量理解，我们把冒泡排序的演变过程，给大家展示

//测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
        //创建要给80000个的随机的数组
        int[] arr = new int[80000];
        for(int i =0; i < 80000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }

Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);

//测试冒泡排序
        bubbleSort(arr);

Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是=" + date2Str);

//System.out.println("排序后");
        //System.out.println(Arrays.toString(arr));

// 第二趟排序，就是将第二大的数排在倒数第二位

for (int j = 0; j < arr.length - 1 - 1 ; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

System.out.println("第二趟排序后的数组");
		System.out.println(Arrays.toString(arr));

// 第三趟排序，就是将第三大的数排在倒数第三位

for (int j = 0; j < arr.length - 1 - 2; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

System.out.println("第三趟排序后的数组");
		System.out.println(Arrays.toString(arr));

// 第四趟排序，就是将第4大的数排在倒数第4位

for (int j = 0; j < arr.length - 1 - 3; j++) {
			// 如果前面的数比后面的数大，则交换
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

System.out.println("第四趟排序后的数组");
		System.out.println(Arrays.toString(arr)); */

}

// 将前面额冒泡排序算法，封装成一个方法
    public static void bubbleSort(int[] arr) {
        // 冒泡排序 的时间复杂度 O(n^2), 自己写出
        int temp = 0; // 临时变量
        boolean flag = false; // 标识变量，表示是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {

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;
                }
            }
            //System.out.println("第" + (i + 1) + "趟排序后的数组");
            //System.out.println(Arrays.toString(arr));

if (!flag) { // 在一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false; // 重置flag!!!, 进行下次判断
            }
        }
    }

}
```

> 运行结果

```
排序前的时间是=2020-02-01 19:25:30
排序后的时间是=2020-02-01 19:25:42
```

[1]: https://lilinchao.com/usr/uploads/2020/02/50279391.png

标签: 数据结构和算法, 排序

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/530.html

上一篇数据结构和算法学习--排序算法简介

下一篇数据结构和算法学习--选择排序

数据结构和算法学习--冒泡排序

评论已关闭

栏目分类

标签云

友情链接申请

数据结构和算法学习--冒泡排序

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请