文章目录

• 一、时间复杂度（判别排序算法优劣的尺度）
• • 1、时间频度介绍和特点
  • 2、时间复杂度计算
  • 3、常见的时间复杂度
  • • 1)、O(1)
    • 2）、O(logn)
    • 3）、O(n)
  • 4、平均时间复杂度
• 二、冒泡排序
• • 1、冒泡算法实现
• 2、冒泡算法优化

一、时间复杂度（判别排序算法优劣的尺度）

1、时间频度介绍和特点

时间频度：算法的时间复杂度与代码中语句执行次数成正比，例如计算1-100的和，代码：

int total=0;
int end=100;
for(int i =1;i<=end;i++){
	total+=i;
	
}

上述代码求和操作100次，再加上当i为101时仍需判断一次，所以时间复杂度T(n)=101

total = (1+end)*end/2;

上述代码时间复杂度T(n)=1
特点：时间复杂度公式可以忽略常数项和低次项

2、时间复杂度计算

1）一般情况下，程序中基本操作语句的重复执行次数是问题规模n的一个函数，称作T(n)。如果存在一个函数f(n)，当n趋向于无穷时，T(n)/f(n)的极限为一个不等于零的常数，则称f(n)是T(n)的同量级函数，用O(f(n))表示T(n)的时间复杂度。
2）T(n)不同时，时间复杂度可能相同
3）计算时间复杂度，只保留最高阶项并去除系数。

3、常见的时间复杂度

0(1) < O(logn) < O(n) < O(nlogn) < 0(n^2) < 0(n^3) < 0(2^n ) < O(n!) < O(n^n)

1)、O(1)

只要代码中没有循环等复杂结构，时间复杂度就为O(1)

2）、O(logn)

int i =1;
while(i<n){
i=i*2;
}

3）、O(n)

for(int i =0;i<100;i++){
	j=i
}

4、平均时间复杂度

二、冒泡排序

1、冒泡算法实现

public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        int len = arr.length;
        int temp=0;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;i<len-1-j;i++){
                if(arr[i]>arr[i+1]){
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            System.out.println("第"+(j+1)+"次冒泡后数组为：");
            printArray(arr);
        }
    }
    //打印数组的方法
    public static void printArray(int[] arr){
        for (int i:arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }

}

代码结果运行如下：

时间复杂度T(n)=n^2

2、冒泡算法优化

优化思路1：在冒泡过程中，有可能出现数组已经排序完成但仍然做无用的循环；
为避免这种情况，当冒泡过程中没有发生位置交换，则应该直接退出循环	

public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        int len = arr.length;
        int temp=0;
        boolean flag = false;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;i<len-1-j;i++){
                if(arr[i]>arr[i+1]){
                    flag = true;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            System.out.println("第"+(j+1)+"次冒泡后数组为：");
            printArray(arr);
            //如果flag仍未false说明一次也没有交换，可以直接退出循环
            if(!flag){
                break;
            }else{
                //重置flag方便下一次判断
                flag=false;
            }
        }




    }
    public static void printArray(int[] arr){
        for (int i:arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }

}

优化思路2：冒泡算法可以封装成一个方法，代码如下：

public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        System.out.println("冒泡前数组为：");
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("冒泡后数组为：");
        System.out.println(Arrays.toString(arr));
     
   }
    public static void bubbleSort(int[] arr){
        int len = arr.length;
        int temp=0;
        boolean flag = false;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;i<len-1-j;i++){
                if(arr[i]>arr[i+1]){
                    flag = true;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            //如果flag仍未false说明一次也没有交换，可以直接退出循环
            if(!flag){
                break;
            }else{
                //重置flag方便下一次判断
                flag=false;
            }
        }
    }

}