冒泡排序和改进的冒泡排序

作为一个学计算机的人，看书的时间总是比动手多，感到非常无奈，今天研究了下最最简单的排序算法：冒泡排序法，以及改进的冒泡排序法。

一.冒泡排序描述

对于一个集合中的所有元素只有两种状态：无序和有序。这里用牛逼程度来界定顺序（当然按大小界定也可以），于是冒泡排序可以描述为：在一个笔直的胡同里每隔一定距离站着一个人，我的任务是去寻找高手，胡同口处的我每遇到一个人就和他比试（可以比身高，体重等等），若我比他牛逼就对他说：“老弟啊你武功不行，咱俩还是换换位置。”若他比我牛逼我就原位不动让他去完成我的任务，并且告诉他我是怎么做的。这样一来，发动一次寻找高手活动就能确定胡同最牛逼的高手在最里面。那么第二次活动肯定能找出第二厉害的高手，并且他的位置就在第一高手后面，以此类推最多经过N次（N就是胡同里的全部人数）活动就能把胡同里的所有人按牛逼程度排序了。

缺点：当小于N次活动时就可能有序了，剩下的活动就是浪费时间。

改进方法：记录每次交换的次数，当交换次数为0时就表示所有元素已经有序。

二.操作

主要就是交换位置。

 

程序如下：

 

//-----------------------------
//题目：冒泡排序
//作者：gyk
//时间：2008-10-2
//-----------------------------

#include <iostream>
using namespace std;

template<typename T>
void exchange(T &a,T &b)
{
    T temp;
    temp = a;
    a = b;
    b = temp;
}
//---------------------------------
template<typename T>
void bublesort(T a[], const int n)
{
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<n-i-1;++j)
        {
            if (a[j]>a[j+1])
            exchange<T>(a[j],a[j+1]);
        }
    }
}
//----------------------------------
template<typename T>
void printresult(T a[],const int n)
{
    for (int i=0;i<n;i++)
    cout<<a[i]<<"\n";
}
int main()
{
    int a[]={9,4,2,8,5,3,1,7,6};
    bublesort<int>(a,9);
    printresult<int>(a,9);
    return EXIT_SUCCESS;
}

改进的冒泡：

//-----------------------------
//题目：冒泡排序（改进）
//作者：gyk
//时间：2008-10-2
//-----------------------------

#include <iostream>
using namespace std;

template<typename T>
void exchange(T &a,T &b)
{
    T temp;
    temp = a;
    a = b;
    b = temp;
}
//---------------------------------
template<typename T>
void bublesort(T a[], const int n)
{
    for (int i=0;i<n;++i)
    {
        int count = 0; //记录交换次数

        for (int j=0;j<n-i-1;++j)
        {
            if (a[j]>a[j+1])
            {
                exchange<T>(a[j],a[j+1]);
                count++;
            }
        }
        cout<<"第"<<i<<"次交换次数："<<count<<"\n";
        if (0==count) //交换次数为0退出循环
        break;
    }
}
//----------------------------------
template<typename T>
void printresult(T a[],const int n)
{
    cout<<"\n"<<"排序结果："<<"\n";
    for (int i=0;i<n;i++)
    cout<<a[i]<<"\n";
}
int main()
{
    int a[]={9,4,2,8,5,3,1,7,6};
    bublesort<int>(a,9);
    printresult<int>(a,9);
    return EXIT_SUCCESS;
}

以上代码在vc6.0下编译运行通过。

总结：动手去做一件看起来很容易的事往往有想不到的困难，编写这些简单代码我出现了如下不爽：交换位置的函数名字本来用swap，结果发现名字冲突，我真切感受到了namespace的作用了，文章中我采用改名字的办法，但实际可这样做namespace gyk{swap()};然后using namespace gyk;即可。当然要去掉using namespace std;在cout前加上std:: 哈哈，这又涉及到作用域问题，看来没有什么是理所当然容易的（包括写这些文字）。