java冒泡排序

文章目录

1、冒泡排序是什么？

 2、冒泡排序是工作原理是什么样的？

 3、如何用java代码来实现呢？

4、for循环嵌套实现冒泡排序

5、时间复杂度 

---

 

1、冒泡排序是什么？

冒泡排序是一种排序算法，通过依次比较两个相邻的元素，如果下一个元素比上一个元素的值大，那么就交互它们的位置，直到比较到数组的一侧为止。

 2、冒泡排序是工作原理是什么样的？

如下图，就是冒泡排序执行过程，可以看出冒泡排序是如何移动的。

 3、如何用java代码来实现呢？

用代码来实现冒泡排序，我们就要思考一下冒泡排序的原理：相邻元素两两比较，大的往后放，第一次完毕，最大值出现在最大索引位置。

首先我们定义一个数组

 int[] arr = { 24, 67, 80, 57, 13 };

这个数组arr一共有5个元素，依次是24、67、80、57、13，我们需要让第一个位置与第二个位置、第二个位置与第三个位置、第三个位置与第四个位置......比较，所以for循环i的初始值为0（数组是根据下标来获取值的，下标从0开始），比较次数为数组长度-1（因为可以通过i+1来获取下一个值，所以最后一个元素13就不用再循环了，否则会出现i+1=5，出现了索引越界异常 。 

3.1第一次比较

          //第一次比较
         for (int i = 0; i arr[i+1]){
                //先定义一个临时变量 将后一个元素放入 使前一个元素进入后一个元素的位置
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
           }
        }

       //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

 第一次比较结果

通过第一次比较，数组里面原本第三个位置的80被移动到了最后面，也是最大值。

3.2第二次比较

因为第二次比较时候，数组的最后一个位置80已经完成了最大值排序，所以就不需要再进行比较了，i的循环范围需要-1.

        //第一次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //第二次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

第二次比较结果

 第二次比较的结果可以看出67被移到了数组的倒数第二个位置，67和80都已经排序成功。然后再进行第三次比较、第四次比较，for循环i的值需要再次-1。

3.3第三、第四次比较

第三次和第四次与上面原理一样，第三次的结果就不再演示，直接看第四次比较。

   //第一次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //第二次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //第三次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //第四次比较
        for (int i = 0; i arr[i+1]){
                int temp=arr[i+1];
                arr[i+1]=arr[i];
                arr[i]=temp;
            }
        }
        //实现遍历
        System.out.print("[");
        for (int x = 0; x < arr.length; x++) {
            if (x == arr.length - 1) {
                System.out.println(arr[x] + "]");
            } else {
                System.out.print(arr[x] + ",");
            }
        }

第四次比较结果

 

 可以看出排序已经完成，数组由小到大依次排列。但是我们需要思考一个问题，我们的代码量好多都是重复的，以后开发的时候肯定不会出现这么多的重复代码，所以我们需要进行代码改进，这里就需要用到for循环的嵌套。

4、for循环嵌套实现冒泡排序

在上面的四次比较我们可以发现一个规律，那就是每多一次比较，for循环i的范围就会-1；四次比较一共-3，那么我们可以在for循环外面再加一次for循环，控制内层for循环i的取值范围，那么外层for循环的j的取值范围就是0到数组长度-1，因为数组长度为5，减去1后为4，但是j<4,是取不到4的，所以j的取值只能是0、1、2、3，刚好符合我们内层for循环i的取值。

//通过for循环嵌套来实现
        for (int j=0;jarr[i+1]){
                    int temp=arr[i+1];
                    arr[i+1]=arr[i];
                    arr[i]=temp;
                }
            }
        }

5、时间复杂度 

冒泡排序的时间复杂度：最好情况是O(n)，最坏情况是O(n*2)。

冒泡排序最好的情况是：数组本身就是顺序排列的，外层循环遍历一次就完成O(n)

冒泡排序最坏的情况是：数组本身就是逆序排列的，内外层遍历O(n*2)

欢迎大家在评论区进行讨论并指正我的不足。