韩顺平 数据结构与算法 （8

1. 基本介绍：

对排序序列从前往后依次比较相邻元素的值，若逆序则交换，使小的在前，大的不断向后直到有更大的或者没有数字时候停止；就行水下的气泡一样。

2. 规则

3. 一共进行数组大小 -1 次大循环

4. 每一次排序的次数在逐渐减少

5. 如果我们发现在某次排序中，没有发生依次交换，可以提前结束冒泡排序【优化】

6. 代码演示——冒泡排序+优化+时间复杂度(8s)

package DataStructures.Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class BubbleSort {
    public static void main(String[] args) {
        

        //测试一个八万的数组的时间复杂度
        //预测O(n^2)
        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("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是" + date1Str);
        
        //---排序---
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        //---排序完毕---
        
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是" + date2Str);
      


    }

    //将前面的冒泡排序算法，封装成一个算法
    public static void bubbleSort(int arr[]) {
        //int arr[] = {3, 9, -1, 10, -2};
        //int arr[] = {3, 9, -1, 10, 20};
        //int arr[] = {1, 2, 3, 4, 5};
        
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;//【优化】标识变量：表示是否进行过交换
            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 == false) {
                //说明在一趟排序中，一次交换都没有发生
                break;
            }
        }
    }
}