冒泡排序-java代码-复杂度分析-优化

冷不防 2023-10-10 10:39 22阅读 0赞

#### 冒泡排序-java代码-复杂度分析-优化 ####

*  冒泡排序核心思想-java代码-复杂度分析-优化
 *   *  1. 冒泡排序核心思想
     *   *  1.1. 输入
         *  1.2. 输出
         *  1.3. 处理过程
     *  2. java代码实现
     *  3. 复杂度分析
     *  4. 优化
     *   *  4.1. 优化思路
         *  4.2. 优化后的代码
         *  4.3. 优化后复杂度分析

## 冒泡排序核心思想-java代码-复杂度分析-优化 ##

### 1. 冒泡排序核心思想 ###

#### 1.1. 输入 ####

一个为排序的整形数组 int\[\] array

#### 1.2. 输出 ####

1.  方法返回void
2.  array已经排好序 这里排序顺序为 从小到大 当然你想从大到小也可以

#### 1.3. 处理过程 ####

*  将数组分为排序部分① 和未排序部分②
 *  外层控制冒泡的次数 通常是数组长度减一
 *  内层循环 在未排序部分中 相邻的数字俩俩比较 如果第一个数比第二个数字大就交换 这样第一次交换之后 最大的数字就会在最后（这里使用array\[j\]>array\[j+1\] ）

### 2. java代码实现 ###

/**
     * 实现该接口的类 可进行排序
     */
    public interface Sortable {
        
        /**
         * 排序算法实现
         * @param array
         */
        public void sort(int[] array);
    }

/**
     * 冒泡排序
     * 像鱼吐泡泡一样 慢慢地向上浮动
     * 双重循环
     * 内循环每次都把最大的或者最小的结果交换到最后或最前
     * 外循环控制循环的次数
     * 时间复杂度分析
     * 
     */
    public class BubbleSort implements Sortable{
        
    
        public void sort(int[] array) {
        
            // 控制冒泡的次数 数组长度总共也就array.length 只要循环array.length-2次就够了
            for (int i=array.length-1; i>0; i--) {
        
                // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                // 在未排序的部门中进行相邻元素的比较 这里通过i进行控制
                for (int j=0; j<i; j++) {
        
                    // 如果第一个元素大于第二个元素 则进行交换
                    if (array[j] > array[j+1]) {
        
                        exchange(array, j, j+1);
                    }
                }
            }
        }
    
        /**
         * 交换数组中的俩个值 位置
         * @param input
         * @param i
         * @param j
         */
        public void exchange(int [] input, int i, int j) {
        
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    
        /**
         * 测试
         * @param args
         */
        public static void main(String[] args) {
        
            int[] array = new int[]{
        2, 1, 3, 5, 6, 7, 12, 51, 10};
            System.out.println("Before-排序前" + Arrays.toString(array));
            Sortable sort = new BubbleSort();
            sort.sort(array);
            System.out.println("After-排序后" + Arrays.toString(array));
        }
    }
    /**
     * result:
     * Before-排序前[2, 1, 3, 5, 6, 7, 12, 51, 10]
     * After-排序后[1, 2, 3, 5, 6, 7, 10, 12, 51]
     *///:~

### 3. 复杂度分析 ###

*  最坏的情况下 O( n^2)
 *  最好的情况下 O(n^2)
 *  平均的复杂度都是O( n^2)

### 4. 优化 ###

#### 4.1. 优化思路 ####

加上一个标志位flag (boolean) 判断在外循环此次中是否有比较交换元素 没有则说明已经排好序 可以退出循环了

#### 4.2. 优化后的代码 ####

import java.util.Arrays;
    
    /**
     * 冒泡排序
     * 像鱼吐泡泡一样 慢慢地向上浮动
     * 双重循环
     * 内循环每次都把最大的或者最小的结果交换到最后或最前
     * 外循环控制循环的次数
     *  当然平均的复杂度都是O( n^2)
     */
    public class BubbleSort implements Sortable{
        
    
        public void sort(int[] array) {
        
            // 控制冒泡的次数 数组长度总共也就array.length 只要循环array.length-2次就够了
            for (int i=array.length-1; i>0; i--) {
        
                // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                boolean flag = true;
                // 在未排序的部门中进行相邻元素的比较 这里通过i进行控制
                for (int j=0; j<i; j++) {
        
                    // 如果第一个元素大于第二个元素 则进行交换
                    if (array[j] > array[j+1]) {
        
                        exchange(array, j, j+1);
                        flag = false;
                    }
                }
                if (flag) {
        
                    break;
                }
            }
        }
    
        /**
         * 交换数组中的俩个值 位置
         * @param input
         * @param i
         * @param j
         */
        public void exchange(int [] input, int i, int j) {
        
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    
        /**
         * 测试
         * @param args
         */
        public static void main(String[] args) {
        
            int[] array = new int[]{
        2, 1, 3, 5, 6, 7, 12, 51, 10};
            System.out.println("Before-排序前" + Arrays.toString(array));
            Sortable sort = new BubbleSort();
            sort.sort(array);
            System.out.println("After-排序后" + Arrays.toString(array));
        }
    }
    /**
     * result:
     * Before-排序前[2, 1, 3, 5, 6, 7, 12, 51, 10]
     * After-排序后[1, 2, 3, 5, 6, 7, 10, 12, 51]
     *///:~

#### 4.3. 优化后复杂度分析 ####

加了flag标志位之后时间复杂度发生改变

*  最坏的情况下 O( n^2)
 *  最好的情况下 O(n)
 *  平均还是O(n^2)

最好的情况是数组已经排好序了 外循环循环一次 内循环循环 n-1 次 结果时间复杂度自然就是O(n)了