7.冒泡排序(优化版本)

一般我们写冒泡排序时都会这么写:

void bubbleSort(T arr[], int n){
    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < n-1-i; j++)
            if(arr[j] > arr[j+1])
                swap(arr[j],arr[j+1]);
    }
}

经过优化的冒泡排序是这样的：

void bubbleSort(T arr[], int n){
    bool swapped;
    do
    {
        swapped = false;
        for( int i = 0; i < n-1; i++ ){
            if( arr[i] > arr[i+1] ){
                swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
    n--;
    }while(swapped)
}

现在我们分别用最差和最优两种情况来分别衡量这两个版本冒泡排序的性能。

首先看最差情况，也就是对一个完全无序的数组进行排序，例如[4,3,2,1].
对于一般版本 需要经过(1+2+3+...+n-1)=n(n-1)/2 次比较操作(即if操作).
对于优化版本 同样需要经过这么多次比较.

我们来测试一下：

test.cpp:
#include <iostream>

using namespace std;

template<typename T>
void bubbleSort_low(T arr[], int n){
    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < n-1-i; j++)
        {
            cout << 1 ;
            if(arr[j] > arr[j+1])
                swap(arr[j],arr[j+1]);
        }
    }
    cout << endl;
}

template<typename T>
void bubbleSort_advance(T arr[], int n){
    bool swapped;
    do{
        swapped = false;
        for( int i = 0; i < n-1; i++ ){
            cout << 2 ;
            if( arr[i] > arr[i+1] ){
                swap( arr[i], arr[i+1] );
                swapped = true;
            }
        }
        n--;
    }while(swapped);

    cout << endl;
}
int main()
{
    int a1[4] = {1,2,3,4};
    int a2[4] = {1,2,3,4};
    int b1[4] = {4,3,2,1};
    int b2[4] = {4,3,2,1};
    bubbleSort_low(b1,4);
    bubbleSort_advance(b2,4);
    return 0;
}

发现两个版本的比较都执行了6次比较 ,将4带入n(n-1)/2这个公式算也是6

也就是说二者在最差情况下的性能是基本相同的（忽略细枝末节的一些影响），其时间复杂度都是O(n^2)级别的。

再来看最优情况，也就是数组完全有序的情况，用[1,2,3,4]测试.

int main()
{
    int a1[4] = {1,2,3,4};
    int a2[4] = {1,2,3,4};
    int b1[4] = {4,3,2,1};
    int b2[4] = {4,3,2,1};
    bubbleSort_low(a1,4);
    bubbleSort_advance(a2,4);
    return 0;
}

我们这样得到的结果是：

发现 low版本执行了6次，advance版本执行了3次
也就是说在最优情况下，第一种版本也是执行了n(n-1)/2 次，时间复杂度依旧是O(n^2).
但第二种版本，i从0迭代到n-2 共执行了n-1次比较操作，在这里就是3次，时间复杂度为O(n).

稍微改一下，加深下理解:

int main()
{
    int a1[4] = {2,1,3,4};
    int a2[4] = {2,1,3,4};
    int b1[4] = {4,3,2,1};
    int b2[4] = {4,3,2,1};
    bubbleSort_low(a1,4);
    bubbleSort_advance(a2,4);
    return 0;
}

得到的结果是这样的：

advance版本执行了5次，第一轮for循环i从0到n-2，执行3次if操作，然后将swapped改为true，接着还是要进到do while语句里，第二轮for循环i从0到n-3，执行2次if操作，这一趟的作用是检查看还有没有逆序对，发现没有就退出了，共执行了5次.
通过这个例子的补充，我们知道了advance版本的冒泡排序不管是完全有序，还是完全无序，它都要执行i从0到n-1的遍历操作来检查一遍是否有逆序对的存在.

小结：
最差情况：
一般冒泡排序 O(n^2)
优化的冒泡排序 O(n^2)

最优情况：
一般冒泡排序 O(n^2)
优化的冒泡排序 O(n)