冒泡排序详细解说

柔光的暖阳◎ 2022-10-28 03:51 163阅读 0赞

## 思路分析 ##

冒泡排序是每次找到一个最大值或者最小值，放到合适的位置上，借助相邻元素比较交换的方式来完成。

具体思路如下：用cur和cur+1两个位置进行比较，如果cur大于cur+1位置的值，那么就将两个位置的值交换，之后让cur+1继续比较交换，直到cur+1等于数组长度的时候为止，这样就可以把整个数组中最大的元素找到，放到了数组末尾，到此就已经完成了第一趟排序。

接着重复以上过程，直到整个数组排序完成

## 图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]  
按照如图所示的思路继续进行后续的第4趟……第n趟冒泡排序，直到排序完成。

## 代码示例 ##

方法一：从前往后进行遍历，就是每次找最大

private static void exchange(int[] array, int bound, int cur) {
        
            int tmp = array[bound];
            array[bound] = array[cur];
            array[cur] = tmp;
        }
        public static void bublesertSort(int[] array){
        
            for (int bound = 0; bound < array.length; bound++){
        
                for (int cur = 0; cur < array.length -1- bound; cur++){
        
                    if (array[cur] > array[cur+1]){
        
                        exchange(array, cur, cur+1);
                    }
                }
            }
        }

方法二：从后往前，就是每次找最小

private static void exchange(int[] array, int bound, int cur) {
        
            int tmp = array[bound];
            array[bound] = array[cur];
            array[cur] = tmp;
        }
     public static void bubbleSort(int[] array){
        
            for (int bound = 0; bound < array.length; bound++){
        
                for (int cur = array.length - 1; cur > bound; cur--){
        
                    if (array[cur-1] > array[cur]){
        
                        exchange(array, cur-1, cur);
                    }
                }
            }
        }

优化：

//优化
        public static void bubbleSort2(int[] array){
        
            boolean flg = false; //没有发生交换
            for (int i = 0; i < array.length; i++){
        
                for (int j = 0; j < array.length - 1 - i; j++){
        
                    if (array[j] > array[j + 1]){
        
                        int tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                        flg = true;
                    }
                }
                if (flg == false){
        
                    break;
                }
            }
        }

## 性能分析 ##

**时间复杂度：**  
最好：O(N) \{数据有序\}  
平均：O(N^2)  
最坏：O(N^2) \{数组逆序\}

**空间复杂度：**  
O(1)

**稳定性：**  
稳定排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221024/731967293b0040178962b531591e14f2.png