改进后的冒泡排序_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 改进后的冒泡排序

改进后的冒泡排序

 2013/9/23 5:26:03  guangqiang  程序员俱乐部  我要评论(0)
  • 摘要:/***改进冒泡排序的两个做法冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数
  • 标签:冒泡排序
class="cpp" name="code">/***
改进冒泡排序的两个做法 冒泡排序(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;
}


 

?

上一篇: 让人大跌眼镜的iPhone 5S保修条款 下一篇: 没有下一篇了!
发表评论
用户名: 匿名