bubblesort2.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>                  //改进的冒泡排序

void output(int table[],int n);        //输出数组的n个元素,略
void swap(int table[],int i,int j);    //交换,略

void bubblesort2(int table[],int n)    //改进的冒泡排序算法
{
    int i=0,j=0,index=0;
    bool exchange=true;                //是否交换的标记
    while(i<n-1 && exchange)           //最多n-1趟排序
    {
        cout<<"第"<<i<<"趟  "<<index<<"~"<<n-i-1<<"  ";
        exchange=false;                //假定元素未交换  
        j=index;                       //起始比较位置 
        while(j<n-i-1)                 //一轮比较、交换
        {
            cout<<table[j]<<"<"<<table[j+1]<<"? ";
            if(table[j]>table[j+1])
            {
                swap(table,j,j+1);     //反序时，交换
                exchange=true;         //更改交换标记  
                cout<<"swap ";
            }
            j++;
            if(!exchange && table[j]<table[j+1])
                index++;
        }
        output(table,n);
        i++;
    }
}
void main()
{
    const int N=8;
    int a[N]={1,2,3,5,8,7,6,5};
    cout<<"N="<<N;
    output(a,N);
    bubblesort2(a,N);
}
/*程序运行结果 ：
N=8  table: 1 2 3 5 8 7 6 5 
第0趟  0~7  1<2? 2<3? 3<5? 5<8? 8<7? swap 8<6? swap 8<5? swap   table: 1 2 3 5 7 6 5 8 
第1趟  3~6  5<7? 7<6? swap 7<5? swap   table: 1 2 3 5 6 5 7 8 
第2趟  3~5  5<6? 6<5? swap   table: 1 2 3 5 5 6 7 8 
第3趟  3~4  5<5?   table: 1 2 3 5 5 6 7 8 
*/

void output(int table[],int n)         //输出数组的n个元素
{
    cout<<"  table: ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<" ";
    cout<<"\n";
}
void swap(int table[],int i,int j)     //交换table[i]、table[j]的值
{                        
    int temp=table[i];
    table[i]=table[j];
    table[j]=temp;
}