冒泡排序（交换排序）

简介：

冒泡排序的基本思想是：设排序序列的记录个数为n，进行n-1次遍历，每次遍历从开始位置依次往后比较前后相邻元素，这样较大的元素往后移，n-1次遍历结束后，序列有序。

例如，对序列(3,2,1,5)进行排序的过程是：共进行3次遍历。

第1次遍历时先比较3和2，交换，继续比较3和1,交换，再比较3和5，不交换，这样第1次遍历结束，最大值5在最后的位置，得到序列(2,1,3,5)。第2次遍历时先比较2和1，交换，继续比较2和3，不交换。

第2次遍历结束时次大值3在倒数第2的位置，得到序列(1,2,3,5)。

第3次遍历时，先比较1和2，不交换，得到最终有序序列(1,2,3,5)。

需要注意的是，如果在某次遍历中没有发生交换，那么就不必进行下次遍历，因为序列已经有序。

实现：

package suanfa;
/*
 * 冒泡排序
 */
public class maopao {
    // 冒泡排序 注意 flag 的作用
    public static void maoPaoSort(int[] array) {

        boolean flag = true;

        for (int i = 0; i < array.length - 1 && flag; i++) {

            flag = false;

            for (int j = 0; j < array.length - 1 - i; j++) {

                if (array[j] > array[j + 1]) {

                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    flag = true;
                }
            }
        }

    }
    
    public static void print(int src[]) {
         for (int i = 0; i < src.length; i++) {
             
                System.out.print(src[i] + " ");
            }
         System.out.println();
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[]= {3,2,1,5};
        print(array);
        maoPaoSort(array);
        print(array);
    }

}

分析：

最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序，不需要进行下一次遍历，所以最佳情况下，时间复杂度为 O(n) 。

最坏情况下冒泡排序需要n-1次遍历，第一次遍历需要比较n-1次，第二次遍历需要n-2次，...，最后一次需要比较1次，最差情况下时间复杂度为 O(n^2) 。