• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

图解冒泡排序及算法优化(Java实现)

开发技术 开发技术 2周前 (09-11) 20次浏览

冒牌排序

基本思想

定义:冒泡排序的英文是bubblesort,它是一种基础的交换排序

原理:每次比较两个相邻的元素,将较大的元素交换至右端 (升序排序)

思路:相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变

案例分析

1、初始的无序数列 {5,8,6,3,9,2,1,7},希望对其升序排序

2、按照思路分析:
图解冒泡排序及算法优化(Java实现)
在经过第一轮交换后,最大的数 9 冒泡到了最右边

图解冒泡排序及算法优化(Java实现)

到此为止,所有元素都是有序的了,这就是冒泡排序的整体思路。
3、冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素,总共遍历(元素数量-1)轮,所以平均时间复杂度是O(n2)。

代码实现

第 1 版代码

public static void bubbleSort(int[] arr){
    if (arr == null || arr.length == 0) return;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 -i; j++) {
            int tmp = 0;
            //升序排序>,降序排序<
            if (arr[j] > arr[j + 1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

使用双循环进行排序。外部循环控制所有的回合,内部循环实现每一轮的冒泡处理,先进行元素比较,再进行元素交换。

第 2 版代码

仍以无序数列 {5,8,6,3,9,2,1,7}为例,我们发现在第 6 轮的时候,数列已经是有序了,但冒泡排序仍然进行了第7轮,可以做一个小优化,在外层循环设置一个哨兵标记isSorted,默认有序,内层循环如果发生交换,则仍为无序

图解冒泡排序及算法优化(Java实现)

public static void bubbleSort(int[] arr){
    if (arr == null || arr.length == 0) return;
    for (int i = 0; i < arr.length - 1; i++) {
        //是否已经有序的标记,默认有序
        boolean isSorted = true;
        for (int j = 0; j < arr.length - 1 -i; j++) {
            int tmp = 0;
            //升序排序>,降序排序<
            if (arr[j] > arr[j + 1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                //发生元素交换,序列仍是无序状态
                isSorted = false;
            }
        }
        if (isSorted){
            break;
        }
    }
}

isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列已然有序,然后直接跳出大循环。

第 3 版代码

以新的无序数列 {3,4,2,1,6,7,8,9}为例,发现前半部分是无序的,而后半部分[6 ,7 ,8 ,9]是有序区间

图解冒泡排序及算法优化(Java实现)

如果以上面的第2版代码执行,会发现只有前半部分的比较是有意义的,而后半部分的有序区间的比较是无意义的

图解冒泡排序及算法优化(Java实现)

怎么避免这种情况?那么可以在每一轮的排序后,记录下来最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区

public static void bubbleSort(int[] arr){
    if (arr == null || arr.length == 0) return;
    //记录记录下来最后一次元素交换的位置
    int lastExchangeIndex = 0;
    //无序数列的边界,每次比较只需要比到这里为止
    int sortBorder = arr.length-1;
    for (int i = 0; i < arr.length - 1; i++) {
        //是否已经有序的标记,默认有序
        boolean isSorted = true;
        for (int j = 0; j < sortBorder; j++) {
            int tmp = 0;
            //升序排序>,降序排序<
            if (arr[j] > arr[j + 1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                //发生元素交换,序列仍是无序状态
                isSorted = false;
                //更新为最后一次交换元素的位置
                lastExchangeIndex = j;
            }
        }
        //更新无序数列的边界
        sortBorder = lastExchangeIndex;
        if (isSorted){
            break;
        }
    }
}

在第3版代码中,sortBorder就是无序数列的边界。在每一轮排序过程中,处于sortBorder之后的元素就不需要再进行比较了,肯定是有序的

算法升级

分析

冒泡算法的每一轮都是从左到右来比较元素,进行单向的位置交换的,是单向的

以新的无序数列 {2,3,4,5,6,7,8,1}为例,按照冒泡排序的算法,排序过程如下:

图解冒泡排序及算法优化(Java实现)

事实上,前面的[2,3,4,5,6,7,8]已经是有序了,只有元素1的位置不正确,却要进行7轮交换。可以将算法从单向交换改为双向交换,排序过程就像钟摆一样,第1轮从左到右,第2轮从右到左,第3轮再从左到右……,这就是鸡尾酒排序.

鸡尾酒排序

图解鸡尾酒排序:

图解冒泡排序及算法优化(Java实现)

经过2轮交换(虽然实际上已经有序,但是流程并没有结束),进入第3轮交换从左到右进行,1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变……6和7比较,位置不变。
没有元素位置进行交换,证明已经有序,排序结束。

public static void cockTailSort(int[] arr){
    if (arr == null || arr.length == 0) return;
    // 记录右侧最后一次交换的位置
    int lastRightExchangeIndex = 0;
    // 记录左侧最后一次交换的位置
    int lastLeftExchangeIndex = 0;
    // 无序数列的右边界,每次比较只需要比到这里为止
    int rightSortBorder = arr.length - 1;
    // 无序数列的左边界,每次比较只需要比到这里为止
    int leftSortBorder = 0;

    //i设置为1,代表从第1轮开始
    for (int i = 1; i < arr.length; i++) {
        boolean isSorted = true;
        //奇数,从左到右
        if (i % 2 != 0) {
            for (int j = leftSortBorder; j < rightSortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    //发生元素交换,序列仍是无序状态
                    isSorted = false;
                    //更新为右侧最后一次交换元素的位置
                    lastRightExchangeIndex = j;
                }
            }
        } else {
            //偶数,从右到左
            for (int j = rightSortBorder; j > leftSortBorder; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    //发生元素交换,序列仍是无序状态
                    isSorted = false;
                    //更新为左侧最后一次交换元素的位置
                    lastLeftExchangeIndex = j;
                }
            }
        }
        //更新无序数列的左边界
        leftSortBorder = lastLeftExchangeIndex;
        //更新无序数列的右边界
        rightSortBorder = lastRightExchangeIndex;
        if (isSorted) {
            break;
        }
    }

}

优缺点:鸡尾酒排序的优点是能够在特定条件下,减少排序的回合数;而缺点也很明显,就是代码量几乎增加了1倍。

应用场景无序数列中大部分元素已经有序

参考图书:《漫画算法—小灰的算法之旅》

欢迎关注我的掘金


喜欢 (0)