冒泡排序最好时间复杂度为什么是O

Question

如题所述

Answer 1

冒泡排序的最佳时间复杂度是O(n)，即是在序列本来就是正序的情况下。

在最好情况下，6和7总不被执行，5每次只被执行1次。因此，

Answer 2

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序

代码实现

在冒泡排序的过程中，如果某一趟执行完毕，没有做任何一次交换操作，比如数组[5,4,1,2,3]，执行了两次冒泡，也就是两次外循环之后，分别将5和4调整到最终位置[1,2,3,4,5]。此时，再执行第三次循环后，一次交换都没有做，这就说明剩下的序列已经是有序的，排序操作也就可以完成了，来看下代码　

/**
     * 冒泡排序
     *
     * @param arr     */
    public static void bubbleSort(int[] arr) {        
        for (int i = 0; i < arr.length - 1; i++) {            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }            
            if (flag) {                
            break;
            }
        }
    }

根据上面这种冒泡实现，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）。综合来看，冒泡排序最好时间复杂度为是O(n).

Answer 3

冒泡排序的最好时间复杂度为O（n），但原始算法是达不到的，需要做简单优化，在外层循环中加入flag量进行判断——若本轮遍历没有发生任何一次交换，则终止循环。

具体实现参考如下（JS）

function bubbleSort(arr) {
    let loopTimes = 0
    for (let i = 0, len = arr.length; i < len; i++) {
        let finished = true
        for (let j = 0, len = arr.length - i - 1; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                finished = false;
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            }
        }
        loopTimes++;
        if (finished)
            break
    }
    return loopTimes 
}

let arr = [2, 3, 9, 4, 5]
let res = bubbleSort(arr)
console.log('loopTimes:' + bubbleSort(arr))
console.log('the Array after sorting:' + arr)

更详细的解释可参考——冒泡排序优化（T-T欢迎关注我的博客，多多指教，嘤嘤嘤）

Answer 4

忘了....