首页 > 代码库 > 冒泡排序详解

冒泡排序详解

冒泡排序可以说是排序中一个十分重要的内容,很多时候都会遇到,比如面试,考试等。下面就来写一写冒泡排序,也可以加深一下自己的理解。

冒泡排序原理,依次比较相邻的两个元素,把较大的元素移至后端;每趟排序找出较大的值放在后端。

给定一个数组,例如[2,8,4,6,1];

第一趟排序:将8移至后端

  第一次排序:[2,8,4,6,1];  //比较2和8,位置不变

  第二次排序:[2,4,8,6,1];  //比较8和4,将8移至4的后面

  第三次排序:[2,4,6,8,1];  //比较8和6,将8移至6的后面

  第四次排序:[2,4,6,1,8];  //比较8和1,将8移至1的后面

第二趟排序:将6移至后端

  第一次排序:[2,4,6,1,8];  //比较2和4,位置不变

  第二次排序:[2,4,6,1,8];  //比较4和6,位置不变

  第三次排序:[2,4,1,6,8];  //比较6和1,将6移至1的后面

第三趟排序:将4移至后端

  第一次排序:[2,4,1,6,8];  //比较2和4,位置不变

  第二次排序 : [2,1,4,6,8];  //比较4和1,将4移至1的后面

第四次排序:将2移至后端

  第一次排序:[1,2,4,6,8];  //比较2和1,将2移至1的后面

冒泡排序代码如下:

for(int i=0;i<arr.length-1;i++){
    for(int j=0;j<arr.length-1-i;j++){
    if(arr[j]>arr[j+1]){
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        }        
    }
}
            

时间复杂度:

1.如果数组是顺序的,则一趟排序即可,进行n-1次比较,时间复杂度为O(n);

2.如果数组是逆序的,则需要n-1趟排序,每次n-i趟比较,时间复杂度为O(n2);

综上,冒泡排序平均时间复杂度为O(n2);

 

冒泡排序详解