简单排序-2.冒泡排序

Bubble Sort

image

1.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

for(j=0;j<arraysize-1;j++)
{
    if(array[j]>array[j+1])
        swap(array,j,i+1);
}

2. 循环针对所有的元素重复以上的步骤，除了最后一个。

for(i=arraysize-1;i>0;i--)
{
    for(j=0;j<i;j++)
    {
        if(array[j]>array[j+1])
            swap(array,j,i+1);
    }
}

时间复杂度 O(n2), 最好的时候O(n)

上面的程序时间复杂度无论什么时候都是是O(n2)，所以要优化

优化

bool flag;
for(i=arraysize-1;i>0;i--)
{
    flag = true;
    for(j=0;j<i;j++)
    {
        if(array[j]>array[j+1])
        {
            swap(array,j,i+1);
            flag = false;
        }
    }
    if(flag)
        break;
}