0082 时间复杂度，冒泡排序

/*
 * 排序也称排序算法（Sort Algorithm）
 * 排序是将一组数据，依指定的顺序进行排列的过程。
 * 
 * 排序分类
 * 1.内部排序：将需要处理的所有数据都加载到内存存储器中进行排序（使用内存）
 *         插入排序
 *             1.直接插入排序
 *             2.希尔排序
 *         选择排序
 *             3.简单选择排序
 *             4.堆排序
 *         交换排序
 *             5.冒泡排序
 *             6.快速排序
 *         7.归并排序
 * 
 *         8.基数排序
 * 
 * 2.外部排序：数据量过大，无法全部加载到内存，借助外部存储进行排序（使用内存和外存结合）
 * 
 * 
 * 算法的时间复杂度
 * 
 *     度量一个程序（算法）执行时间的两种方法
 *     1.事后统计
 *         方法可行，但需要实际运行该程序，且所得时间的统计量依赖于计算机硬件
 *     2.事前统计
 *         通过分析某个算法得时间复杂度来判断哪个算法更优
 * 
 *     时间频度
 *     一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就多。
 *     一个算法中的语句执行次数称为语句频度或时间频度，记为T（n）
 *     可以忽略常数项、低次项和系数
 * 
 *     如计算1-100所有数字之和，设计两种算法：(for循环和直接计算)
 * 
 *    for循环
 *     int total = 0;
 *     int end = 100;
 *  for(int i = 1;i <= end;i++){
 *      total += i;    
 *  }
 *  T(n)=n+1
 *  
 *  直接计算
 *  total = (1+end)*end/2
 *  T(n)=1
 *  
 *  时间复杂度
 *  1.一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T（n）表示，
 *    若有某个辅助函数f(n)，使得当n趋于无穷大时，T（n）/f(n)的极限值为不等于零的常数
 *    则称f(n)是T（n）的同数量级函数。记为T（n）=O(f(n))
 *    称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度
 *    
 *  2.T（n）不同，但时间复杂度可能相同。如T（n）=n²+7n+6与T（n）=3n²+2n+2 
 *    它们的T（n）不同，但时间复杂度相同，都为O（n²）
 *  
 *  3.计算时间复杂度的方法
 *      1.用常数1代替运行时间中的所有加法常数
 *      2.修改后的运行次数函数中，只保留最高阶项
 *      3.去除最高阶项的系数
 *  
 *  常见时间复杂度
 *  1.常数阶O（1）
 *  2.对数阶O（log₂n）
 *  3.线性阶O（n）
 *  4.线性对数阶O（nlog₂n）
 *  5.平方阶O（n²）
 *  6.立方阶O（n³）
 *  7.k次方阶O（n^k）
 *  8.指数阶O（2ⁿ）
 *  
 *  时间复杂度从大到小依次为：O（1）  *  随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
 *  所以应尽可能避免使用指数阶的算法
 *  
 *  1.常数阶O（1）
 *      int i = 1;
 *      int j = 2;
 *         i++;
 *      j++;
 *      int m = i + j;
 *  无论代码执行了多少行，只要没有循环等复杂结构，代码执行时并不随着某个变量的增长而增长，时间复杂度就是O（1）
 *  
 *  2.对数阶O（log₂n）
 *      int i = 1;
 *      while(i < n){
 *          i = i * 2;
 *      }
 *  在while循环里，每次都将i乘以2，i距离n越来越远了，假设循环x次后，i就大于2，此时循环退出。
 *  即2的x次方=n，x=log₂n,即当循环log₂n次后，代码结束，所以时间复杂度为O（log₂n）
 *  若i=i*3,则是O（log₃n）
 *  
 *  3.线性阶O（n）
 *  for(i = 1;i <= n;++i){
 *      j = i;
 *      j++;
 *  }
 *  for循环里的代码会执行n次，因此消耗时间是随着n的变化而变化，时间复杂度为O（n）
 *  
 *  4.线性对数阶O（nlog₂n）
 *  for(m = 1;m < n;m++){
 *      i = 1;
 *      while(i < n){
 *            i = i * 2;      
 *      }
 *  }
 *  将时间复杂度为O（log₂n）的代码循环n遍，那么时间复杂度就为n * O（log₂n） 即O（nlog₂n）
 *  
 *  5.平方阶O（n²）
 *  for(x = 1;i <= n;x++){
 *      for(i = 1;i <= n;i++){
 *          j = i;
 *          j++;
 *      }
 *  }
 *  把O（n）的代码在嵌套循环一遍，时间复杂度就为O（n*n）,即O（n²），如果把n改为m，则时间复杂度为O（m*n）
 *     立方阶和k次方阶相当于3层n循环，k层n循环...
 * 
 *     平均时间复杂度和最坏时间复杂度
 *     1.平均时间复杂度是指所有可能的输入实例均以等概率出现的概率下，该算法的运行时间
 *     2.一般讨论的时间复杂度是最坏时间复杂度。
 *       原因是：最坏时间复杂度是算法在任何输入实力上运行时间的界限，保证了算法的运行时间不会比最坏情况更长
 *     3.平均时间复杂度和最坏时间复杂度是否一致，和算法有关
 * 
 *     空间复杂度
 *     1.类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity）定义为
 *       该算法所耗费的存储空间，也是问题规模n的函数
 *     2.空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
 *       有的算法需要占用的临时工作单元数与解决问题规模n有关，随着n的增大而增大，当n较大时，将占用较多的存储单元
 *     3.在做算法分析时，主要讨论时间复杂度，从用户使用体验上看，更看重的是程序执行的速度。
 *       一些缓存产品和算法本质就是用空间换时间。
 *  
 */

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

/*
 * 冒泡排序
 *     通过待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值
 *     若发现逆序则交换，使值较大的元素逐渐从前移到后，就像水里的气泡一样向上冒
 * 
 * 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说明序列有序
 * 因此要在排序过程中设置一个flag判断元素是否进行过交换，从而减少不必要的比较
 * 
 * 冒泡排序过程
 * 原始：3，9，-1，10，-2
 * 第一次排序
 * （3与9比较）
 * 3，9，-1，10，-2
 * （9与-1比较）
 * 3，-1，9，10，-2
 * （9与10比较）
 * 3，-1，9，10，-2
 * （10与-2比较）
 * 3，-1，9，-2,10    //确定了10
 * 
 * 第二次排序
 * （3与-1比较）
 * -1，3，9，-2，10
 * （3与9比较）
 * -1，3，9，-2，10
 * （9与-2比较）
 * -1，3，-2，9，20    //确定了9
 * 
 * 第三次排序
 * （-1和3比较）
 * -1，3，-2，9，10
 * （3和-2比较）
 * -1，-2，3，9，10     //确定了3
 * 
 * 第四次排序
 * （-1和-2比较）
 * -2，-1，3，9，10    //确定了-1
 * 
 * 总结
 * 1.一共进行数组大小-1次循环
 * 2.每一次排序的次数在逐渐减少
 * 3.优化：如果发现在某次排序中没有发生交换，可提前结束冒泡排序
 */
public class BubbleSorting_ {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
      
        //测试冒泡排序的速度
        int[] arr2 = new int[80000];
        for(int i = 0;i < 80000;i++) {
            arr2[i] = (int)(Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间=" + date1Str);
        
        bubbleSort(arr2);
        
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间=" + date2Str);
    }
/*
        //第一次排序
        int temp = 0;//临时变量
        for(int j = 0;j < arr.length - 1 - 0;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 - 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));
        
        //第四次排序
        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));
*/    
/*
        int temp = 0;//临时变量
        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("第" + (i+1) + "次排序");
            System.out.println(Arrays.toString(arr));
        }
*/        
        //优化：设置标识变量，并封装成方法
    public static void bubbleSort(int[] arr) {
        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 == false) {//说明没有发生交换
                break;
            }else {
                flag = false;//重置flag，进行下次判断
            }
        }
    }
}