冒泡排序面试题

001什么是冒泡排序？

冒泡排序是在遍历数组的过程中，每次都要比较连续相邻的元素，如果某一对相邻元素是降序（即前面的数大于后面的数），则互换它们的值，否则，保持不变。由于较大的值像“气泡”一样逐渐浮出顶部，而较小的值沉向底部，所以叫冒泡排序。

002冒泡排序的代码实现？

具体实现参考如下源代码：

//冒泡排序
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)+"轮排序结果：");  
        display(list);
    }
}

003冒泡排序时间复杂度？

冒泡排序的时间复杂度是O(N²)。 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢? N-1次！因此，冒泡排序的时间复杂度是O(N²)。

004冒泡排序稳定性？

冒泡排序是稳定的算法，它满足稳定算法的定义。所谓算法稳定性指假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

005冒泡排序的改进版实现。

/*
 * 冒泡排序(改进版)
 *
 * 参数说明:
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
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]中最大的数据放在末尾
        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; // 若发生交换，则设标记为1
            }
        }

        if (flag == 0)
            break; // 若没发生交换，则说明数列已有序。
    }
}