改进的冒泡排序法

经典冒泡排序：

void BubbleSort_1(int a[], int size)  
{  
    for (int i = 0; i < size -1; i++)  
    {  
        for (int j = size - 1; j > i ; j--)  
        {  
            if (a[j-1] > a[j])  
            {  
                int temp = a[j-1];  
                a[j-1] = a[j];  
                a[j] = temp;  
            }  
        }  
    }  
}

优化1、在第二层循环时，如果交换操作没有发生，那么证明现在这个序列就是有序的，就可以跳出这个循环。

void BubbleSort_2(int a[], int size)  
{  
    bool bSwaped = true;  
    for (int i = 0; i < size -1; i++)  
    {  
        // 每次先重置为false  
        bSwaped = false;  
        for (int j = size - 1; j > i ; j--)  
        {  
            if (a[j-1] > a[j])  
            {  
                int temp = a[j-1];  
                a[j-1] = a[j];  
                a[j] = temp;  

                bSwaped = true;  
            }  
        }  
        // 如果上一次扫描没有发生交换，则说明数组已经全部有序，退出循环  
        if (!bSwaped)  
            break;  
    }  
}

优化2、如果现在有序的区间是［1，i］，第二层循环扫描的就是［i，n］，这样交换操作就一定是发生在［i，n］这个区间中，记上次交换的位置为l，i《＝l 《＝ n，那么可以确定［1，l］都是有序的，这样就可以缩小下次扫描区间为［l，n］。

void BubbleSort_3(int a[], int size)  
{  
    int l = 0,lt = 0;  
    for (int i = 0; i < size - 1; i++)  
    {  
        l = lt;  
        for (int j = size - 1; j > l; j--)  
        {  
            if (a[j - 1] > a[j])  
            {  
                int temp = a[j - 1];  
                a[j - 1] = a[j];  
                a[j] = temp;  

                lt = j;  
            }  
        }  
        //如果没有发生交换，证明已经有序
        if (l == lt)  
            break;  

    }  
}

wangwangwar / daily-notes

改进的冒泡排序法 #34