改进后的冒泡排序

/***
改进冒泡排序的两个做法　冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 

　　由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 
***/

 

现在让我们来提升算法的效率：

首先来看一个例子：

41 67 34 0 69 24 78 58 62 64

第一趟排序为   41 34 0 67 24 69 58 62 64 78

第二趟排序为   34 0 41 24 67 58 62 64 69 78

第三趟排序为   0 34 24 41 58 62 64 67 69 78

第四趟排序为   0 24 34 41 58 62 64 67 69 78

每趟排序的结果是最大数移动到最后一个位置：

（1）根据此结果我们每次比较之后都可以为下一次减少一次比较，因为最大数已经沉底，所以最后一位就不用比较了。

因此在内层循环中我们每次都可以减少一次循环。

（2）根据冒泡排序的思想本来按道理是要比较 n-1趟的 上诉的例子为9趟。但是在第四趟中就已经排序完成。如果在继续

下去就等于做无用功了，因此我们可以再第四趟排序中就可以退出循环了，所以我们可以增加一个变量 bool flags=true;

将其初始化为true，当发生数据的交换时候就赋予false值。如果在本趟排序中就没有发生一次交换则就在外层循环中跳出去。

 

一个完整的例子：

//////////////////////////////
///////sort .h file

template<typename type>
void Swap(type &p,type &q)
{
    type temp=p;
    p=q;
    q=temp;
}

//由小到大进行排序 
template<typename type>
void bubbling_sort(type a[],int n)
{
    int i,j;
    bool flags=true;
    for( i=0; i < n-1; i++ )
    {
        for( j=0; j < n-1-i; j++ )
        {
            if( a[j] > a[j+1] )
            {
                Swap(a[j],a[j+1]);
                flags=false;
            }
        }
        if( flags )
            break;
        else
            flags=true;
    }
} 


 

 

////////////////////////////////////////////

//////main.cpp file

#include <cstdlib>
#include <iostream>
#include "sort.h"

using namespace std;


int main(int argc, char *argv[])
{
    int a[10];
    int n;
    
    cout<<"排序前"<<endl; 
    
    for( int i=0;i<10;i++ )
    {
        n=rand()%100;
        a[i]=n;
        cout<<a[i]<<" ";
    }
    cout<<endl;
    
    cout<<"排序后"<<endl;
    bubbling_sort(a,10);
    
    for( int j=0;j<10;j++ )
        cout<<a[j]<<" ";
    cout<<endl;
    
    cout << "Press the enter key to continue ...";
    cin.get();
    return EXIT_SUCCESS;
}


 

 更多内容 请参考我的个人博客 http://ismartstudio.com/

评论

4 楼 guangqiang 2013-03-20  

图受各种 写道

lxy2520 写道

不好意思， Arrays.sort()是在Java中，不知道C++有木有

c++有sort方法，需要include<algorithm>

不过我这是在研究数据结构呢 需要最基本的算法和程序代码实现 ，假设面试让你做冒泡排序你会怎么回答？

3 楼 图受各种 2013-03-20  

lxy2520 写道

不好意思， Arrays.sort()是在Java中，不知道C++有木有

c++有sort方法，需要include<algorithm>

2 楼 lxy2520 2013-03-20  

不好意思， Arrays.sort()是在Java中，不知道C++有木有

1 楼 lxy2520 2013-03-20  

有空你测试一下Arrays.sort()方法 和你改进以后的排序算法的性能。你会被测试结果折服的