【057-week3】

[wangfanstar]

暴力解法

从左至右扫描，当看到一个左边大于右边的一对，就将左右对换，再退后一步进行比较，看对换后是否还存在左边大于右边的情形，一直到初始的处，然后继续向右进行，一直到n。

A[n] 0 --> n  [0,n)
for (int i = 1; i < n; i++)
{
    if ((A[i-1] > A[i]) && 0 < i)
        {swap(A[i-1],A[i]); i--;}
}

暴力改进

当后退一定步数k后，再次前进可以前进k步，不用再按1依次前进

int i = 1, j = 1;
while(i < n)
    {
        if ((1 <= i) && (A[i-1] >　A[i]) )
        {
            swap(A[i-1],A[i]);
            i--;
            j++;
        }
        else
        {
            i += j;
            j = 1;
        }
    }

起泡排序

一次扫描将最大的放到最右

int bubble(int []A,int n)
{
    while(n--)
    {
        for(int i = 0; i < n; i++)
        {
            if(A[i] > A[i+1])
                swap(A[i-1],A[i]);
        }
    }
    return 0;
}

起泡改进

如果没有交换，说明已经有序，直接返回成功

int bubble(int [] A, int n)
{
    bool sorted = true;
    while(n--)
    {
        for(int i = 0; i < n; i++)
        {
            if(A[i] > A[i+1])
            {
                swap(A[i-1],A[i]);
                sorted = false;
            }
        }
        if (sorted == true)
            return 0;
    }
}

起泡改进2

记录下最后交换的位置，最后交换的位置到未尾已经有序，不用再比较交换。当下一次交换时，不用再遍历到未尾，只要遍历到最后交换的位置即可

int bubble(int []A, int n)
{
    int last = n;
    while(last--)
    {
        for(int i = 0; i < last; i++)
        {
            if（A[i] > A[i+1])
            {
                swap(A[i],A[i+1]);
                last = i;
            }
        }
    }
    return 0;
}

起泡梳理版

分成起泡过程和排序两部分，起泡部分单独成一个函数。范围改成从[lo,hi)。last元素表示，逆序对只存在last左边，不包括last，初始值为lo。

int bubble(int lo, int hi)
{
    int last = lo;
    while(lo++ < hi)
    {
        if(A[lo-1] > A[lo])
        {
            swap(A[lo-1],A[lo])
            last = lo;
        }
    }
    return last;
}
//下一次起泡时只须从[lo, last) 即可。
void bubblesort(int [] A, int lo, int hi)
{
    while(lo < (hi = bubble(lo,hi)));
    return ;
}