冒泡排序详细解说

小雨的分享社区

发布于 2022-10-26 15:06:13

3120

发布于 2022-10-26 15:06:13

文章被收录于专栏：小雨的CSDN

思路分析

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

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

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

图解

按照如图所示的思路继续进行后续的第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;
            }
        }
    }