冒泡排序

图示

原理

Code

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的后一对元素。
3. 每一轮冒泡能将参与该轮冒泡的最大值元素移动到该轮的末尾。

如：7 3 4 8 1 2 5 9 6 0
10个数要冒泡9轮，n个数冒n-1轮；
每冒一轮，减少一个数参与冒泡；
每轮m个数参与冒泡，要比较m-1次；
外层循环控制冒泡的轮数；
内层循环控制该轮冒泡要比较的次数；

实现

java

public static void _从左往右找大数往右冒(Comparable a[]){

    for (int i = 0; i < a.length - 1; i++) { //需要 元素个数-1 轮冒泡

        //该轮参与冒泡的元素个数 = 元素个数-i
        //该轮元素需要比较的次数 = 该轮参与冒泡的元素个数-1 = 元素个数-i-1
        for (int j = 0; j < a.length-i-1; j++) {
            if(_是否大于(a[j],a[j+1])){
                _交换(a, j,j+1);
            }
        }

    }
}

性能

如6个数： [6,5,4,3,2,1]

需要比较的次数

Code

第一轮的6需要比较5次

第二轮的5需要比较4次

...

第五轮的2需要比较1次

同理需要交换的次数

Code

第一轮的6需要交换5次

第二轮的5需要交换4次

...

第五轮的2需要交换1次

N个数需要比较总次数：（N-1）+（N-2）+（N-3）+ … + 2 + 1 = ((N-1)+1) * (N-1)/2 = N^2/2 - N/2

N个数需要交换总次数：（N-1）+（N-2）+（N-3）+ … + 2 + 1 = ((N-1)+1) * (N-1)/2 = N^2/2 - N/2

总的执行次数为：N^2/2 - N/2 + N^2/2 - N/2 = N^2 - N

根据大O记法，时间复杂度为 O(N^2)

稳定性

稳定, 两个相同元素, 等于时候不交换, 这两个相同元素的顺序还是不变的。