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

记录学习经典排序算法

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

No1 冒泡排序

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

    /**
     * 冒泡排序
     * 相邻两个数进行对比交换位置,进行length-1 个回合每个回合找到一个最大值
     * @param arr
     */
    private static void bubbleSort(int[] arr) {

        /**
         *  外训坏决定对比回合数
         */
        for (int i = 0; i < arr.length - 1; i++) {

            /**
             * 内循环决定内部对比的次数 (每一回合确定最大,所以减去第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));
        }
    }

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

    /**
     * 冒泡排序
     * 相邻两个数进行对比交换位置,进行length-1 个回合每个回合找到一个最大值
     * @param arr
     */
    private static void newBubbleSort(int[] arr) {

        /**
         *  外训坏决定对比回合数
         */
        for (int i = 0; i < arr.length - 1; i++) {

            /**
             * 内循环决定内部对比的次数 (每一回合确定最大,所以减去第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));
        }
    }

No2 插入排序