Java实现冒泡排序——一看就会

桃扇骨 2023-01-07 10:16 102阅读 0赞

### 目录 ###

*  冒泡排序
 *   *  代码实现：
     *  优化
     *  具体实现：
     *  更高效的方法

# 冒泡排序 #

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。  
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。  
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

例如：将一个无需的数组升序排列：**arr\[\] = \{ 2, 7, 8, 3, 10, 4, 0, 1, 9, 6, 5 \}**  
使用冒泡排序法：  
第一趟：2 , 7 , 3 , 8 , 4 , 0 , 1 , 9 , 6 , 5 , 10  
第二趟：2 , 3 , 7 , 4 , 0 , 1 , 8 , 6 , 5 , 9 , 10  
**…**  
第一趟：0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10  
**每一趟都会将数组中的最大数，移动到最后面去**

## 代码实现： ##

import java.util.Arrays;
    
    /** * 冒泡排序 */
    public class bubbleSortDemo { 
        public static void bubbleSort(int[] arr) { 
            //控制趟数
            for (int i = 0; i < arr.length - 1; i++) { 
                //控制每一趟的排序
                for (int j = 0; j < arr.length - 1 - i; j++) { 
                    //判断大小，将大的放在最后面
                    if (arr[j] > arr[j + 1]) { 
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                    }
                }
            }
        }
        public static void main(String[] args) { 
            int[] array = { 2, 7, 8, 3, 10, 4, 0, 1, 9, 6, 5};
            //排序数组
            bubbleSort(array);
            //打印排序后的数组
            System.out.println(Arrays.toString(array));
        }
    }

具体结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

## 优化 ##

我们知道在冒泡排序中，n个数据，需要比较n-1趟，每趟比上一次少1个数据。

但是，当我们遇到待排序的数组时候，已经有序，或者近乎有序的时候，不需要移动数据，或者移动很少的数据，但是按照上面的排序，仍需要移动很多趟。  
那么如何解决这个问题呢？

## 具体实现： ##

我们可以定义一个Boolean的flag，当一次排序没有交换过数据，那么证明数组已经有序。  
（需要注意的是，这个flag进去需要修改状态，否则只进行一次，或者不进行就跳出循环了）

import java.util.Arrays;
    
    /** * 我们知道在冒泡排序中，n个数据，需要比较n-1趟，每趟比上一次少1个数据。 * 但是，当我们遇到待排序的数组时候，已经有序，或者近乎有序的时候，不需要移动数据，或者移动很少的数据，但是按照上面的排序，仍需要移动很多趟。 * 那么如何解决这个问题呢？ * 我们可以定义一个Boolean的flag，当一次排序没有交换过数据，那么证明数组已经有序。 */
    public class bubbleSortDemo1 { 
    
        public static void bubbleSort(int[] arr) { 
            boolean flag = true;
            //控制趟数
            for (int i = 0; i < arr.length - 1; i++) { 
                //进来先修改，不然会不进行排序
                flag = false;
                //控制每一趟的排序
                for (int j = 0; j < arr.length - 1 - i; j++) { 
                    //判断大小，将大的放在最后面
                    if (arr[j] > arr[j + 1]) { 
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                        flag = false;
                    }
                    if (flag == true) { 
                        break;
                    }
                }
            }
        }
    
        public static void main(String[] args) { 
            //int[] array = {2, 7, 8, 3, 10, 4, 0, 1, 9, 6, 5};
            int[] array = { 1, 2, 4, 3, 5, 6, 7, 8, 9};
            //排序数组
            bubbleSort(array);
            //打印排序后的数组
            System.out.println(Arrays.toString(array));
    
        }
    }

具体结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]

## 更高效的方法 ##

java中，在import java.util.Arrays;（我们之前使用的toString就在这个包中）Arrays主要是对数组进行操作，包中提供了更方便的排序方法。包含各种类型：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]  
所以，上面代码可以简化成：

import java.util.Arrays;
    
    /** *利用Arrays工具进行排序 */
    public class bubbleSortDemo2 { 
    
        public static void main(String[] args) { 
            int[] array = { 2, 7, 8, 3, 10, 4, 0, 1, 9, 6, 5};
            //int[] array = {1, 2, 4, 3, 5, 6, 7, 8, 9};
            //排序数组
            Arrays.sort(array);
            //打印排序后的数组
            System.out.println(Arrays.toString(array));
        }
    
    }

![在这里插入图片描述][20210117100000347.png]  
这种方法，大大简化了代码量，但是我们也需要弄清楚原理。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221119/244148f845bc48c39244e948f0982c0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221119/436fbb9b5bd441a4956f619bf0bbaa81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221119/66bedba5ff2c4bbfbfd553f9fd0421ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221119/5b03407bae854888a32e03090b37ec51.png
[20210117100000347.png]: https://img-blog.csdnimg.cn/20210117100000347.png