乐趣区

看动画学算法之排序冒泡排序

jiezi

简介

排序可能是所有的算法中最最根底和最最罕用的了。排序是一个十分经典的问题，它以肯定的程序对一个数组（或一个列表）中的项进行从新排序。

排序算法有很多种，每个都有其本身的长处和局限性。

明天咱们来学习最最简略的冒泡排序算法。

冒泡排序的原理

冒泡排序的原理很简略，咱们设想一下一个一个的气泡上浮的过程。

假如咱们有八个数字 29,10,14,37,20,25,44,15 要进行排序。

咱们先用一个动画图来直观的察看一下整个冒泡排序的过程：

排序共进行八轮，每一轮都会做两两比拟，并将较大的元素右移，就像冒泡一下。

一轮完结之后，八个元素中最大的那个元素 44 将会挪动到最左边。

而后再反复其余的几轮。最终失去一个齐全排序的数组。

也能够这样看：

第一轮是将八个元素中的最大值 44 替换挪动到最右地位。
第二轮是将八个元素中的次大值 37 替换挪动到最右地位。
以此类推。

冒泡排序算法的 java 实现

咱们先看一个最简略的冒泡算法：

public class BubbleSort {public void doBubbleSort(int[] array){log.info("排序前的数组为:{}",array);
        // 外层循环, 遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            // 内层循环，两两比拟，选中较大的数字，进行替换
            for(int j=0; j<array.length-1; j++){if(array[j]>array[j+1]){
                    // 替换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("第 {} 轮排序后的数组为:{}", i+1, array);
        }
    }

    public static void main(String[] args) {int[] array= {29,10,14,37,20,25,44,15};
        BubbleSort bubbleSort=new BubbleSort();
        bubbleSort.doBubbleSort(array);
    }

}

这个算法就是两层遍历，外层遍历示意的是进行的轮数。内层遍历示意的是每一轮的排序。

咱们看下输入后果：

冒泡算法的第一次改良

剖析下面的遍历过程，咱们能够发现，第一次排序之后，44 曾经放到最左边的地位了，曾经排好序了。

第二次排序之后，37 也曾经排好序了。每过一轮，外部循环须要比拟的次数就能够减一。

这就意味着，在外部循环的时候，咱们只须要进行 array.length-i- 1 次比拟就能够了。

批改代码如下：

public class BubbleSort1 {public void doBubbleSort(int[] array){log.info("排序前的数组为:{}",array);
        // 外层循环, 遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            // 内层循环，两两比拟，选中较大的数字，进行替换, 最初的 i 个数字曾经排完序了，不须要再进行比拟
            for(int j=0; j<array.length-i-1; j++){if(array[j]>array[j+1]){
                    // 替换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("第 {} 轮排序后的数组为:{}", i+1, array);
        }
    }

    public static void main(String[] args) {int[] array= {29,10,14,37,20,25,44,15};
        BubbleSort1 bubbleSort=new BubbleSort1();
        bubbleSort.doBubbleSort(array);
    }

}

运行后果：

能够看到运行后果其实没什么不同，只不过咱们少做了几次比拟。

冒泡算法的第二次改良

从下面的后果，咱们能够看到实际上第 5 轮排序过后就曾经排序实现了。然而咱们依然进行了第 6，7 次排序。

有没有什么方法能够判断排序是不是曾经实现了呢？

咱们考虑一下，在外部循环中，咱们是进行两两比拟，而后替换地位。

如果在某一次遍历中，没有进行交互，这就意味着排序曾经实现了。

所以咱们能够再引入一个 flag 来做判断。

public class BubbleSort2 {public void doBubbleSort(int[] array){log.info("排序前的数组为:{}",array);
        // 外层循环, 遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            // 增加一个 flag，如果这一轮都没有排序，阐明排序曾经完结，能够提前退出
            boolean flag=false;
            // 内层循环，两两比拟，选中较大的数字，进行替换, 最初的 i 个数字曾经排完序了，不须要再进行比拟
            for(int j=0; j<array.length-i-1; j++){if(array[j]>array[j+1]){
                    // 替换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
            log.info("第 {} 轮排序后的数组为:{}", i+1, array);
            if(!flag)
            {log.info("本轮未产生排序变动，排序完结");
                return;
            }
        }
    }

    public static void main(String[] args) {int[] array= {29,10,14,37,20,25,44,15};
        BubbleSort2 bubbleSort=new BubbleSort2();
        bubbleSort.doBubbleSort(array);
    }

}

运行后果如下：

从后果咱们能够看到少了一轮排序，晋升了速度。

冒泡排序的工夫复杂度

尽管咱们能够在冒泡的时候进行一些性能优化，然而基本上还是要进行嵌套的两次遍历。遍历次数近似的 =n*n，所以冒泡排序算法的工夫复杂度是 O(n²)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-bubble-sort/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！

退出移动版