冒泡排序

冒泡排序

（一）排序过程分析

    现在有一个数组，共有六个元素，{1,4,7,2,3,5}，要求把他们按照从小到大的顺序排列，每一趟排序将较大的值交换到最右边，下面进行排序过程分析。

（二）排序过程分析

第一趟比较.png

    第一趟比较结束，得到{1,4,2,3,5,7}，共比较5次；

第二趟比较.png

    第二趟比较结束，得到{1,2,3,4,5,7}，共比较4次；

第三趟比较.png

    第三趟比较结束，得到{1,2,3,4,5,7}，共比较3次；

第四趟比较.png

    第四趟比较结束，得到{1,2,3,4,5,7}，共比较2次；

第五趟比较.png

    第五趟比较结束，得到{1,2,3,4,5,7}，共比较1次；
    至此，已经无法再进行比较，该序列已经有序，冒泡排序结束。由上述过程可知，冒泡排序的本质就是元素之间的交换，共6个数，执行5趟排序比较，若有n个数，则是执行n-1趟比较，每一趟从左到右比较相邻的两个数，如果大的数在左边则进行交换，在每一趟比较结束后，该趟最大的数在最右边。
    时间复杂度分析：第一趟比较，是n个数进行比较；第二趟比较，是n-1个数进行比较；第三趟比较，是n-2个数进行比较......所以这是一个等差数列求和最后得O(N2)（2是N的上标值，因为简书不支持latex）。

（二）Java代码

public class BubbleSort {

public static void main(String[] args) {
    int[] shus= {1,4,7,2,3,5};
    //外面比较的是几趟
    for (int i = 1; i <= shus.length-1; i++) {
        //第i趟从a[0]开始到a[n-i+1]都与他们的下一个数比较
        for (int j = 0; j < shus.length-i; j++) {
            if (shus[j] > shus[j+1]) {
                int temp = shus[j];
                shus[j] = shus[j+1];
                shus[j+1] = temp;
            }
        }
    }
    print(shus);
}

public static void print(int shus[]) {
    for (int i = 0; i < shus.length; i++) {
        System.out.print(shus[i] + " ");
    }
}
}