冒泡排序的三种实现方法

冒泡排序的基本思想是：第i趟起泡排序是从第1到n-i+1一次比较相邻两个记录的关键字，并在“逆序”时交换记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序需进行k（1<=k
最原始的起泡排序实现代码如下：
  

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

优化1：下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
  代码如下：
  

int BubbleSort2(int a[],int n)
{
    int j,k;
    bool flag;
    k=n;
    flag=true;
    while(flag)
    {
        flag=false;
     for(j=0;j<k-1;j++)
        {
         if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        k--;

    }
    return n-k;
}

优化2：再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

 代码如下：
   

void BubbleSort3(int a[],int n)
{
    int j,k;
    int flag;

    flag=n;
    while(flag>0)
    {
        k=flag;
        flag=0;
     for(j=0;j<k-1;j++)
        {
         if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                flag=j+1;
            }
        }

    }
}

  完整的测试代码如下：
     
   

#include<iostream>
using namespace std;


void swap(int *a,int *b)
{
    *a=*a^*b;
    *b=*b^*a;
    *a=*a^*b;

}

void BubbleSort3(int a[],int n)
{
    int j,k;
    int flag;

    flag=n;
    while(flag>0)
    {
        k=flag;
        flag=0;
     for(j=0;j<k-1;j++)
        {
         if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                flag=j+1;
            }
        }

    }
}

int main()
{
    int a[8];
    printf("please input the number:\n");
    for(int i=0;i<8;i++)
        scanf("%d",&a[i]);
    BubbleSort(a,8);
    for(i=0;i<8;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;

}