排序算法 - 冒泡排序


theme: qklhk-chocolate highlight: vs2015

简介


冒泡排序是一种非常主流的排序算法,冒泡排序的英文(Bubble sort),它是一种基础的交换排序。


原理 : 比较两个相邻的元素,将值大的元素交换至右端。

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


举例说明:要排序数组:int[] array={5,8,6,3,9,2,1,7};

在这里插入图片描述

第一趟排序:

第一次排序:5 和 8 比较,5 小于 8 ,位置不变: 5,8,6,3,9,2,1,7

第二次排序:8 和 6 比较,8 大于 6 ,交换位置: 5,6,8,3,9,2,1,7

第三次排序:8 和 3 比较,8 大于 3 ,交换位置: 5,6,3,8,9,2,1,7

第四次排序:8 和 9 比较,8 小于 9 ,位置不变: 5,6,3,8,9,2,1,7

第五次排序:9 和 2 比较,9 大于 2 ,交换位置: 5,6,3,8,2,9,1,7

第六次排序:9 和 1 比较,9 小于 1 ,交换位置: 5,6,3,8,2,1,9,7

第七次排序:9 和 7 比较,9 小于 7 ,交换位置: 5,6,3,8,2,1,7,9

第二趟排序:

第一次排序:5 和 6 比较,5 小于 6 ,位置不变: 5,6,3,8,2,1,7,9

第二次排序:6 和 3 比较,6 大于 3 ,交换位置: 5,3,6,8,2,1,7,9

第三次排序:6 和 8 比较,6 小于 8 ,位置不变: 5,6,3,8,2,1,7,9

第四次排序:8 和 2 比较,8 大于 2 ,交换位置: 5,6,3,2,8,1,7,9

第五次排序:8 和 1 比较,8 大于 1 ,交换位置: 5,6,3,2,1,8,7,9

第六次排序:8 和 7 比较,8 大于 7 ,交换位置: 5,6,3,2,1,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 5,6,3,2,1,7,8,9

第三趟排序:

第一次排序:5 和 6 比较,5 小于 6 ,位置不变: 5,6,3,2,1,7,8,9

第二次排序:6 和 3 比较,6 大于 3 ,交换位置: 5,3,6,2,1,7,8,9

第三次排序:6 和 2 比较,6 大于 2 ,交换位置: 5,3,2,6,1,7,8,9

第四次排序:6 和 1 比较,6 大于 1 ,交换位置: 5,3,2,1,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 5,3,2,1,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 5,3,2,1,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 5,3,2,1,6,7,8,9

第四趟排序:

第一次排序:5 和 3 比较,5 大于 3 ,交换位置: 3,5,2,1,6,7,8,9

第二次排序:5 和 2 比较,5 大于 2 ,交换位置: 3,2,5,1,6,7,8,9

第三次排序:5 和 1 比较,5 大于 1 ,交换位置: 3,2,1,5,6,7,8,9

第四次排序:5 和 6 比较,5 小于 6 ,位置不变: 3,2,1,5,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 3,2,1,5,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 3,2,1,5,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 3,2,1,5,6,7,8,9

第五趟排序:

第一次排序:3 和 2 比较,3 大于 2 ,交换位置: 2,3,1,5,6,7,8,9

第二次排序:3 和 1 比较,3 大于 1 ,交换位置: 2,1,3,5,6,7,8,9

第三次排序:3 和 5 比较,3 小于 5 ,位置不变: 2,1,3,5,6,7,8,9

第四次排序:5 和 6 比较,5 小于 6 ,位置不变: 2,1,3,5,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 2,1,3,5,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 2,1,3,5,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 2,1,3,5,6,7,8,9

第六趟排序:

第一次排序:2 和 1 比较,2 大于 1 ,交换位置: 1,2,3,5,6,7,8,9

第二次排序:2 和 3 比较,2 小于 3 ,位置不变: 1,2,3,5,6,7,8,9

第三次排序:3 和 5 比较,3 小于 5 ,位置不变: 1,2,3,5,6,7,8,9

第四次排序:5 和 6 比较,5 小于 6 ,位置不变: 1,2,3,5,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 1,2,3,5,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 1,2,3,5,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 1,2,3,5,6,7,8,9

第七趟排序:

第一次排序:1 和 2 比较,1 小于 2 ,位置不变: 1,2,3,5,6,7,8,9

第二次排序:2 和 3 比较,2 小于 3 ,位置不变: 1,2,3,5,6,7,8,9

第三次排序:3 和 5 比较,3 小于 5 ,位置不变: 1,2,3,5,6,7,8,9

第四次排序:5 和 6 比较,5 小于 6 ,位置不变: 1,2,3,5,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 1,2,3,5,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 1,2,3,5,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 1,2,3,5,6,7,8,9

排序结果 : 1,2,3,5,6,7,8,9

/**
 * 冒泡排序
 * 定义 : 我们要把相邻的两个元素两两比较,当一个元素大于右侧相邻元素时,
 *        交换他们的位置 : 当一个元素小于或等于相邻右侧元素时,位置不变
 */
public class demo1 {

    public static void main(String[] args) {
        int array[] = {5,8,6,3,9,2,1,7};

        sortBig(array);
        System.out.println("大到小排列:"+ Arrays.toString(array));

        sortSmall(array);
        System.out.println("小到大排列:"+ Arrays.toString(array));
    }

    /**
     * 从大到小排序方法
     * @param array 数组
     */
    private static void sortBig(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[i] > array[j]){
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }

    }


    /**
     * 从小到大排序
     * @param array 数组
     */
    private static void sortSmall(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[j] > array[j +1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

}

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

执行结果:

大到小排列:[9, 8, 7, 6, 5, 3, 2, 1]

小到大排列:[1, 2, 3, 5, 6, 7, 8, 9]

优化

让我们回顾一下刚才描述的排序细节,{5,8,6,3,9,2,1,7}这个数列,当排序算法分别执行到第6、第7轮时

在这里插入图片描述

很明显可以看出,经过第六轮的时候,整个数列已经是有序的了。可是排序算法仍然执行了第七轮

在这种情况下,如果能判断出数列已经有序,并做出标记,那么剩下的几轮排序就不必执行了,可以提前结束工作。


冒泡排序代码优化:

/**
 * 冒泡排序优化
 * 定义 : 我们要把相邻的两个元素两两比较,当一个元素大于右侧相邻元素时,
 *        交换他们的位置 : 当一个元素小于或等于相邻右侧元素时,位置不变
 */
public class demo1 {

    public static void main(String[] args) {
        int array[] = {5,8,6,3,9,2,1,7};

        sortBig(array);
        System.out.println("大到小排列:"+ Arrays.toString(array));

        sortSmall(array);
        System.out.println("小到大排列:"+ Arrays.toString(array));
    }

    /**
     * 从大到小排序方法
     * @param array 数组
     */
    private static void sortBig(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //标记
            boolean flag = true;
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[i] > array[j]){
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    //有元素在交换,所以不是有序的
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }

    }


    /**
     * 从小到大排序
     * @param array 数组
     */
    private static void sortSmall(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //标记
            boolean flag = true;
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[j] > array[j +1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    //有元素在交换,所以不是有序的
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }

}

利用 boolean 变量 flag 作为标记。如果本轮排序中,元素有交换,则列表是无序的,如果没有元素交换,则是有序的,直接跳出大循环, 进一步提升了性能。



个人博客地址:http://blog.yanxiaolong.cn 『纵有疾风起,人生不言弃』

end
  • 作者:yxl(联系作者)
  • 发表时间:2021-05-07 15:25
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载栈主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论