冒泡排序学习总结_冒泡排序选择排序的算法优化实验小结

作者：黑客灵魂 | 2024-07-14 10:31:01

踩

冒泡排序选择排序的算法优化实验小结

1、算法描述

1、算法描述

这里有一个无序数组，接下来我要用冒泡的方式对其进行排序，冒泡排序的关键是相邻的两个元素进行比较。

比如说刚开始索引 0 和索引 1 进行比较，如果是前一个小于后一个，它的位置可以不动。

这里3是大于2的所以交换位置。

然后比较索引 1 和索引 2 ，3 比4小不用交换位置，后面的以此类推。

到这里我们就看到最大的7已经移到了数组的最后，相当于已经把最大的元素已经冒泡成功了，完成了一轮冒泡。

接下来就是重复这个排序的动作，直到所有元素排序完成。

2、算法实现


package com.jie.bubbling;
 
import java.lang.reflect.Array;
import java.util.Arrays;
 
/**
 * @description:冒泡排序
 * @author: jie
 * @time: 2022/2/8 19:44
 */
public class Bubbling {
    public static void main(String[] args) {
        int[] a = {5,9,3,7,2,1,8,4};
        //调用方法
        bubble(a);
    }
    /**
     * @description:实现
     * @author: jie 
     * @time: 2022/2/8 19:48
     */
    public static void bubble(int[] a){
        //比较的次数等于i<数组a的长度-1
        for (int j = 0; j < a.length-1; j++) {
            //一轮冒泡 比较的次数等于i<数组a的长度-1
            for (int i=0;i<a.length-1;i++){
                //如果前一个元素大于后一个元素，就交换位置
                if (a[i] > a[i+1]) {
                    //交换位置
                    swap(a,i,i+1);
                }
            }
            System.out.println("第"+j+"轮冒泡"+Arrays.toString(a));
        }
    }
    /**
     * @description:排序方法
     * @author: jie
     * @time: 2022/2/8 19:46
     */
    public static void swap(int[] a,int i,int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

测试结果：

这里初步实现了冒泡排序算法，但是还有很多优化的空间，我们继续往下看。

3、算法优化

3.1 减少内层循环比较次数

我们看上图可以发现，每一轮的冒泡都要比较6次，但是是不是每轮冒泡都需要比较6次呢？不是。

因为我们第一轮冒泡以后，最大的 9 已经冒泡成功了，那下一轮冒泡的时候 9 就不需要进行比较了，没有意义，因为9已经是最大了，所以第二轮冒泡要比一轮冒泡少比较一次，后面的以此类推。

所以我们现在改进一下，改进方法也非常简单。

我们这里利用外层循环 j 这个变量，j 一开始是0,所以第一轮循环，它并不会影响我们的冒泡次数，但随着 j 不断的增长，第二轮冒泡的时候在 a.length-1 的基础上再 -j , 这样就达到我们比较次数逐次递减的效果。

测试结果：

3.2 减少冒泡次数

细心的大家可能已经发现，其实我们在第4轮冒泡完成以后，数据已经有序了，那我们已经完全没有必要进行后续的两次冒泡。

如果我某一轮冒泡两个相邻元素比较比较，没有发生一次交换，说明它整个已经有序了，我们就可以根据这个有没有发生交换来进行判断。

代码：


package com.jie.bubbling;
 
import java.lang.reflect.Array;
import java.util.Arrays;
 
/**
 * @description:冒泡排序
 * @author: jie
 * @time: 2022/2/8 19:44
 */
public class Bubbling {
    public static void main(String[] args) {
        int[] a = {5,9,3,7,2,1,8,4};
        //调用方法
        bubble(a);
    }
    /**
     * @description:实现
     * @author: jie
     * @time: 2022/2/8 19:48
     */
    public static void bubble(int[] a){
        //比较的次数等于i<数组a的长度-1
        for (int j = 0; j < a.length-1; j++) {
            //是否发生交换  false==没有交换
            boolean swapped  = false;
            //一轮冒泡 比较的次数等于i<数组a的长度-1
            for (int i=0;i<a.length-1-j;i++){
                //如果前一个元素大于后一个元素，就交换位置
                if (a[i] > a[i+1]) {
                    //交换位置
                    swap(a,i,i+1);
                    //发生交换了 true
                    swapped = true;
                }
            }
            // 如果这一轮冒泡结束了，没有发生交换，说明数组有序了，退出循环
            if(!swapped){
                break;
            }
            System.out.println("第"+j+"轮冒泡"+Arrays.toString(a));
        }
    }
    /**
     * @description:排序方法
     * @author: jie
     * @time: 2022/2/8 19:46
     */
    public static void swap(int[] a,int i,int j){
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

测试结果：

3.3 进一步优化


package com.jie.bubbling;
 
import java.lang.reflect.Array;
import java.util.Arrays;
 
/**
 * @description:冒泡排序
 * @author: jie
 * @time: 2022/2/8 19:44
 */
public class Bubbling {
    public static void main(String[] args) {
        int[] a = {5,2,7,4,1,3,8,9};
        //调用方法
        bubble(a);
    }
 
    /**
     * @description:实现
     * @author: jie
     * @time: 2022/2/8 19:48
     */
    public static void bubble(int[] a) {
        int n = a.length - 1;
        while (true) {
            // 表示最后一次交换索引位置
            int last = 0;
            for (int i = 0; i < n; i++) {
                System.out.println("比较次数" + i);
                //如果前一个元素大于后一个元素，就交换位置
                if (a[i] > a[i + 1]) {
                    //交换位置
                    swap(a, i, i + 1);
                    //发生交换了 把 i 赋值给last
                    last = i;
                }
            }
            n = last;
            System.out.println("第轮冒泡" + Arrays.toString(a));
            if (n == 0) {
                break;
            }
        }
    }
 
    /**
     * @description:排序方法
     * @author: jie
     * @time: 2022/2/8 19:46
     */
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可。

总结

文字描述：

依次比较数组中相邻两个元素大小，若 a[j] > a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后

重复以上步骤，直到整个数组有序

优化方式：

每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】