001什么是冒泡排序？

冒泡排序是在遍歷數(shù)組的過程中，每次都要比較連續(xù)相鄰的元素，如果某一對相鄰元素是降序（即前面的數(shù)大于后面的數(shù)），則互換它們的值，否則，保持不變。由于較大的值像“氣泡”一樣逐漸浮出頂部，而較小的值沉向底部，所以叫冒泡排序。

002冒泡排序的代碼實現(xiàn)？

具體實現(xiàn)參考如下源代碼：

//冒泡排序
public static void bubbleSort(int[] list){
    int n=list.length;
    for(int i=1;i<n;i++){//總共比較n-1趟
        for(int j=0;j<n-i;j++){//第i趟比較n-i次
            if(list[j]>list[j+1]){
                int temp;
                temp=list[j];
                list[j]=list[j+1];
                list[j+1]=temp;				
            }
        }

        System.out.print("第"+(i)+"輪排序結(jié)果：");  
        display(list);
    }
}

003冒泡排序時間復(fù)雜度？

冒泡排序的時間復(fù)雜度是O(N²)。 假設(shè)被排序的數(shù)列中有N個數(shù)。遍歷一趟的時間復(fù)雜度是O(N)，需要遍歷多少次呢? N-1次！因此，冒泡排序的時間復(fù)雜度是O(N²)。

004冒泡排序穩(wěn)定性？

冒泡排序是穩(wěn)定的算法，它滿足穩(wěn)定算法的定義。所謂算法穩(wěn)定性指假設(shè)在數(shù)列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。則這個排序算法是穩(wěn)定的！

005冒泡排序的改進版實現(xiàn)。

/*
 * 冒泡排序(改進版)
 *
 * 參數(shù)說明:
 *     a -- 待排序的數(shù)組
 *     n -- 數(shù)組的長度
 */
public static void bubbleSort2(int[] a, int n) {
    int i, j;
    int flag; // 標記

    for (i = n - 1; i > 0; i--) {

        flag = 0; // 初始化標記為0
        // 將a[0...i]中最大的數(shù)據(jù)放在末尾
        for (j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                // 交換a[j]和a[j+1]
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;

                flag = 1; // 若發(fā)生交換，則設(shè)標記為1
            }
        }

        if (flag == 0)
            break; // 若沒發(fā)生交換，則說明數(shù)列已有序。
    }
}