冒泡排序

原理：比较两个相邻的元素，将值大的元素交换至右端（升序）。

步骤：

• 第一步，比较第一个数与第二个数的大小，将大的数放到后面

• 第二步，比较第二个数与第三个数的大小，将大的数放到后面，依次下去，直到最后两个数比较完成。

• 第三步，重复第一与第二步直到全部完成排序。

例子：int[] arr={5,2,6,0,9};经行冒泡排序

过程：

第一趟排序：从5开始

• 第一次排序，5比2大，则调换位置，完成之后的排序为:          2 5 6 0 9

• 第二次排序，6比5大，不要调换位置，完成之后的排序为：       2 5 6 0 9

• 第三次排序，6比0大，要调换位置，完成之后的排序为:          2 5 0 6 9

• 第四次排序，9比6大，不要调换位置，完成之后的排序为：         2 5 0 6 9

---

第二趟排序：从2开始

• 第一次排序，2比5小，不要调换位置，完成之后的排序为：　　　　　   　2 5 6 0 9

• 第二次排序，5比6小，不要调换位置，完成之后的排序为：　　　　　　　2 5 6 0 9

• 第三次排序，0比6小，要调换位置，完成之后的排序为：　　　　　　　　2 5 0 6 9

• 第四次排序，6比9小，不要调换位置，完成之后的排序为：　　　　　　　2 5 0 6 9

---

第三趟排序：从2开始

• 第一次排序，2比5小，不要调换位置，完成之后的排序为：　　　　　　　2 5 0 6 9

• 第二次排序，0比5小，要调换位置，完成之后的排序为：　　　　　　　　2 0 5 6 9

• 第三次排序，5比6小，不要调换位置，完成之后的排序为：　　　　　　　2 0 5 6 9

• 第四次排序，6比9小，不要调换位置，完成之后的排序为：　　　　　　　2 0 5 6 9

---

第四趟排序：从2开始

• 第一次排序，0比2小，要调换位置，完成之后的排序为：　　　　　　　　0 2 5 6 9

• 第二次排序，2比5小，不要调换位置，完成之后的排序为：　　　　　　　0 2 5 6 9

• 第三次排序，5比6小，不要调换位置，完成之后的排序为：　　　　　　　0 2 5 6 9

• 第四次排序，6比9小，不要调换位置，完成之后的排序为：　　　　　　　0 2 5 6 9

---

最终的答案为：0 2 5 6 9

---

结论：N个数字经行排序，总共进行N-1趟排序，每趟的排序次数为(N-i)次。

时间复杂度：

1.如果数据是正序排列的，那么第一趟就可以把所有数据排好，则比较次数C和记录移动次数M均达到最小值。

C_min = n-1
M_min = 0

最好的时间复杂度为O_(n)。

2.如果数据是倒序排列的，那么要n-1趟才可以把所有数据排好，则比较次数C和记录移动次数M均达到最大值。

最坏时间复杂度为：O_(n²)。

综上，平均时间复杂度为：O_(n²) 。

优缺点：

• 优点:比较简单，空间复杂度较低，是稳定的；
• 缺点:时间复杂度太高，效率慢；

代码：

public class BubbleSort{
    public static void main(String[] args){        

        int[] arr={5,2,6,0,9};

        System.out.println("排序前的数据:");
        for(int num : arr){
            System.out.print(num+" ");
        }
        //通过两个循环来控制
        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;
                }
            }
        }        
        System.out.println();
        System.out.println("排序后的数据:");
        for(int num : arr){
            System.out.print(num+" ");
        }

    }            
}

结果：