首页 > 代码库 > 冒泡排序

冒泡排序

目录:

  1、为什么要用?(它的好处或优点)

  2、原理是什么?(效果)

  3、怎样去实现?(想马上看代码的同学点这里)

 

为什么要用?

  1、时间复杂度: 平均情况 O(n2)、最坏情况O(n2),最好情况O(n) 

  2、空间复杂度: O(1)

  3、稳定性: 稳定

  4、复杂度:简单 容易实现

  适用场景: 有序部分放到后方,根据大小两两交换,每次遍历都可以将无序部分的最大值过滤到最后,直至完成排序,实现容易,稳定,空间占用少

  不适用场景 : 已排序数据在最后插入小数据

 

原理是什么?

  例如 排序数组 [6 5 3 1 8 7 2 4]

  第一次遍历

      比较 [6 5 3 1 8 7 2 4]

     需交换 [5 6 3 1 8 7 2 4]

 

      比较 [5 6 3 1 8 7 2 4]

     需交换 [5 3 6 1 8 7 2 4]

 

      比较 [5 3 6 1 8 7 2 4]

     需交换 [5 3 1 6 8 7 2 4]

 

      比较 [5 3 1 6 8 7 2 4]

    不需交换 [5 3 1 6 8 7 2 4]

 

      比较 [5 3 1 6 8 7 2 4]

     需交换 [5 3 1 6 7 8 2 4]

 

      比较 [5 3 1 6 7 8 2 4]

     需交换 [5 3 1 6 7 2 8 4]

 

      比较 [5 3 1 6 7 2 8 4]

     需交换 [5 3 1 6 7 2 4 8]

  第二次遍历

    。。。

  可以看到第一次遍历已经把最大的放到最后,第二次遍历则不必再比较最后一个,这样一直遍历下去,可以想象如果最小的在最后,最多遍历 N-1(N为数组长度)次,即可排序完成。如果在本次遍历中没有交换动作,则表明已经排序完成,直接退出不用再遍历到 N-1次。

      

宏观效果:

技术分享

怎样去实现?

java 实现代码:

class bubble_sort  
{
    public static void bubble(int[] arr) {
        int i, j, t,s; // t 交换时中间变量 , s 标示完成状态 
        for (i = 0; i < arr.length - 1; i++){
            s = 0;
            for (j = 0; j < arr.length - 1 - i; j++){
                if (arr[j] > arr[j + 1]) {
                    s = 1;
                    t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    printArray(arr);
                }
            }
            if(s == 0){ //发现 循环中已经没有交换操作了,代表已经完成排序,退出    
                return;
            }
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
         int[] arr = {6,5,3,1,8,7,2,4};
         printArray(arr);
         bubble(arr);
    }
    public static void printArray(int[] arr){
        for(int i : arr){
            System.out.print(i+"   ");
        }
        System.out.println();
    }
}

 

 

输出结果 :

6 5 3 1 8 7 2 4
5 6 3 1 8 7 2 4
5 3 6 1 8 7 2 4
5 3 1 6 8 7 2 4
5 3 1 6 7 8 2 4
5 3 1 6 7 2 8 4
5 3 1 6 7 2 4 8
3 5 1 6 7 2 4 8
3 1 5 6 7 2 4 8
3 1 5 6 2 7 4 8
3 1 5 6 2 4 7 8
1 3 5 6 2 4 7 8
1 3 5 2 6 4 7 8
1 3 5 2 4 6 7 8
1 3 2 5 4 6 7 8
1 3 2 4 5 6 7 8
1 2 3 4 5 6 7 8

 

在线测试地址 :https://www.shucunwang.com/RunCode/java/#id/954b104d0c9dbb6b89f5bac5189f10af

开源代码地址 :https://git.oschina.net/ITxiaoyan/SortAlgorithm

2017-03-25  

冒泡排序