【经典排序算法学习,每天进步一点点】

• • No1 冒泡排序
  • No2 插入排序

冒泡排序是交换排序的一种,因为其过程中类似气泡最小的先浮动出来取名冒泡排序
概述:是一个顺序数组通过相邻的的两个元素对比交换位置,最多进行数组的length-1回合的排序过程

过程极限简化
原数组:[3,2,1] length 3

第一回合 3>2 交换之后 231 3>1交换 结果 [2,1,3]
第二回合 2>1 交换之后 123 (上回合确定了3是最大没必要继续对比对比) 结果 [1,2,3]

总结 过程 2和回合 leng-1 ,每个回合冒确定一个相对最大值 所以内循环 次数为 leng-1-i

    
    private static void bubbleSort(int[] arr) {

        
        for (int i = 0; i < arr.length - 1; i++) {

            
            for (int j = 0; j < arr.length - i - 1; j++) {

                
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;

                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

冒泡排序的优化
增加一个标志如果循环中没有发生交换说明数组已经有序,结束排序

    
    private static void newBubbleSort(int[] arr) {

        
        for (int i = 0; i < arr.length - 1; i++) {

            
            boolean flag = false;
            // 如果循环中没有发生交换说明数组已经有序,结束排序
            for (int j = 0; j < arr.length - i - 1; j++) {
                
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;

                }
            }
            if(!flag){
                break;
            }
            System.out.println(Arrays.toString(arr));
        }
    }