排序(一)冒泡排序你真的会吗?

Myth丶恋晨 2022-12-10 07:25 112阅读 0赞

数据结构与算法 想必大家是处于既快乐 又痛苦的感觉

快乐在于做出题目 一次运行成功后的喜悦

痛苦在于 绞尽脑汁 却还是做不出来

今天说的是冒泡排序

冒泡排序可一说是非常基础了

但是开始学的时候 我又处于一种似懂非懂的状态

好像明白了 过了一段时间 又给忘记了

不知道你们会不会有这样一种感觉呢？

其实就是没有真正的理解

首先分享一张图片  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]

大家都知道 冒泡排序的时间复杂度为O² 其实就是两次循环就行了

我们不能死记硬背

思路是这样的

![2805d79b536e985cc561339a5d8c6a6a.png][]

按从小到大排列的话 找到最大的 下次循环就不需要看最大元素了

所以大循环是递减的

小循环跟随大循环 递增

以arr表示某个数组

for(int i=arr.length-1;i>0;i--){ 
            for(int j=0;j<i;j++){ 
                if(arr[j]>arr[j+1]){ 
                	//交换①
                    //int temp=arr[j];
                    //arr[j]=arr[j+1];
                    //arr[j+1]=temp; 
    			}
            }
    }

其实我认为核心的不是这个交换算法 而是for循环的终止条件

很关键 否则很容易出现数组越界

i>0 原先认为 应该是i>=0 后一想 其实最后一次循环是没有必要的

因为倒数第二小的元素已经找到后 剩下的元素必定是最小的 放在第一位

第二个 j<i 这个也挺有意思的 之前我考虑到j+1会使得数组越界 但发现多虑了

因为j是随着i走的 i最大正好是数组最大下标 j<i 把j扣的死死的

j最大是与i相差一个单位 j+1就与i相等 不会导致数组越界

有时我们应该关注这些细节的部分 这些细节部分 才是让我们真正成长的

分割线----------------------------------------------------------------------------------------------------------------------

补充一下 交换法改良了下 用了异或运算 这是个很牛逼的算法

但不知道为什么 测试的时候没看出来有多大的差别。。。。。。

还有冒泡可以在循环里加一个判断 当前面元素没有大于后面元素时 则跳出循环 不进行后面的比较了 稍微节省了些步骤

当然 冒泡是比较初级的 但也是学习的基础 要好好学习。

public static void sort1_2(int[] arr) { 
            int c=0;
            boolean flag=false;
            for (int i = arr.length-1; i >0; i--) { 
                for (int j = 0; j < i; j++) { 
                    c++;
                    //判断是否前一个元素大于后一个元素 若没得大 不比较了 直接跳出
                    if(arr[j]>arr[j+1]){ 
                        flag=true;
                        arr[j]^=arr[j+1];
                        arr[j+1]^=arr[j];
                        arr[j]^=arr[j+1];
                    }
                }
                if(!flag){ 
                    break;
                }else { 
                    flag=false;
                }
            }
            System.out.println(Arrays.toString(arr)+" "+c);
        }

ps: 学习不能急躁 越快越慢 越慢越快 脚踏实地才是硬道理

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0968b3f66c004304ae888050e640fb8f.png
[2805d79b536e985cc561339a5d8c6a6a.png]: /images/20221123/fcafc00afb534c9f8c774a5bdedbfc15.png