day09-冒泡排序+优化

排序算法（SortAlgorithm）

image.png

算法时间复杂度总结：

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
希尔排序	$O(n^1.3)$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
基数排序	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	稳定

概念:时间频度和时间复杂度

时间频度

时间频度T(n):一个算法中的语句执行次数称为语句的频度或时间频度。

时间复杂度

时间复杂度 f(n)：T(n) = o(F(n))
时间复杂度表示的是一个数量级，并不是一个具体的值。

时间频度估算时间复杂度规则：

忽略常数项。
忽略低次项。
忽略系数。

T(n) = 2n^2+3n+3
忽略常数项
T(n) = 2n^2+3n
忽略低次项
T(n) = 2n^2
忽略系数
T(n) = n^2 = f(n)

即T(n) = 2n^2 + 3n + 3的时间复杂度为n^2的级别的。

tips：for循环会因为最后一次判断而多一次执行。

常见的时间复杂度：

image.png

常数阶：O(1)
对数阶：O(log2n)
线性阶：O(n)
线性对数阶：O(nlog2n)
平方阶：O(n^2)
立方阶：O(n^3)
K次方阶：O(n^k)
指数阶：O(2^n)

一定要避免指数阶的算法！！！！！

冒泡排序

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

原理：

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

通过观察冒泡排序的过程我发现如下结论：

只要遍历 array.length-1 次
每次遍历的数量在减少第n趟只要交换到第array.length-1-n 个元素
本次遍历没有发生过交换就说明顺序已经正确。（优化）

bubbleSort

 public static void bubbleSort(int[] array){
       int temp = 0;
       Long count = 0L;
       for (int i = 0; i < array.length-1; i++) {//
           for (int j = 0; j < array.length -1 - i; j++) {
               count++;
               if (array[j]>array[j+1]){
                   flage=true;
                   temp = array[j];
                   array[j] = array[j+1];
                   array[j+1] = temp;
               }
           }
           if (!flage){
               break;
           }else {
               flage = false;
           }
       }
       System.out.println("count(执行次数)"+count);
   }
}

bubbleSort（优化）

本次遍历没有发生过交换就说明顺序已经正确。做一下判断跳出循环即可。

 public static void bubbleSort(int[] array){
       int temp = 0;
       boolean flage = false;
       Long count = 0L;
       for (int i = 0; i < array.length-1; i++) {//
           for (int j = 0; j < array.length -1 - i; j++) {
               count++;
               if (array[j]>array[j+1]){
                   flage=true;
                   temp = array[j];
                   array[j] = array[j+1];
                   array[j+1] = temp;
               }
           }
           if (!flage){
               break;
           }else {
               flage = false;
           }
       }
       System.out.println("count(执行次数)"+count);
   }
}

完整测试代码：

public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*80000);
        }
        bubbleSort(arr);
    }

    public static void bubbleSort(int[] array){
        int temp = 0;
        boolean flage = false;
        Long count = 0L;
        for (int i = 0; i < array.length-1; i++) {//
            for (int j = 0; j < array.length -1 - i; j++) {
                count++;
                if (array[j]>array[j+1]){
                    flage=true;
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            if (!flage){
                break;
            }else {
                flage = false;
            }
        }
        System.out.println("count(执行次数)"+count);
    }
}

最后编辑于：2020.07.23 19:00:09