`

改进后的冒泡排序

阅读更多
/***
改进冒泡排序的两个做法 冒泡排序(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/

1
1
分享到:
评论
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()方法 和你改进以后的排序算法的性能。你会被测试结果折服的

相关推荐

    冒泡排序及其改进算法C语言实现 冒泡排序及其改进算法C语言实现 冒泡排序及其改进算法C语言实现

    2改进的冒泡排序,在一次冒泡的过程中,如果没有发生交换,则已经有序 3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就无需比较flag...

    冒泡排序法改进前后的比较_冒泡排序法改进前后的比较_

    在"冒泡排序法改进前后的比较.docx"文件中,可能详细列举了不同情况下基本冒泡排序与改进冒泡排序的运行时间、比较次数和交换次数。通过对具体数据的对比,我们可以直观地看到改进后的冒泡排序在大多数情况下都有更...

    冒泡排序改进(追踪最后一次比较避免不必要比较)

    冒泡排序的改进,在里层循环中,追踪最后一次比较,避免不必要的比较,算法课后题

    冒泡排序-排序过程 冒泡排序-排序过程

    这种改进可以显著提高冒泡排序在部分有序或已有序数组上的性能。例如,在给定的数组 `[4, 5, 7, 1, 2, 3]` 排序时,第二趟排序结束后,数组已经完全有序,但是原算法还需要继续执行后续的遍历。通过添加标志变量的...

    python 实现一种改进的冒泡排序,,和折半查找方法

    python 实现一种改进的冒泡排序,简单选择排序的方法。

    实验3 冒泡排序程序

    print("冒泡排序后的数组:", bubble_sort(arr)) ``` 在这个代码中,外层循环控制遍历的轮数,内层循环则进行相邻元素的比较和交换。通过调用`bubble_sort`函数并传入一个未排序的列表,我们可以得到一个已排序的新...

    快速排序,冒泡排序,插入排序,选择排序的四种算法

    有一个模板类写出了快速排序,冒泡排序,插入排序,选择排序四种算法。用的是C++哦

    c++冒泡排序,从小到大排序或者从大到小

    在探讨C++冒泡排序这一知识点时,我们不仅会深入理解冒泡排序的基本原理、算法实现,还会细致分析如何在C++中灵活运用该算法进行数据...同时,通过对冒泡排序的不断优化和改进,可以进一步加深对算法设计与分析的理解。

    冒泡排序讲解.pptx

    8.冒泡排序的改进:冒泡排序可以通过改进来提高效率,例如,使用 flag 变量来记录是否发生了交换,如果没有交换,那么可以提前结束循环。 9.冒泡排序的实践:冒泡排序可以用于解决实际问题,例如,排序一个数组中的...

    冒泡排序源代码下载 冒泡排序源代码下载

    - 用户界面更新:在每一步排序后更新界面元素以反映新的顺序。 如果你有兴趣深入学习或改进这个程序,你可以尝试添加一些优化策略,例如: - **添加标志位**:在一轮遍历后如果没有发生交换,说明序列已经有序,...

    优化冒泡排序和选择排序

    为了解决这个问题,优化后的冒泡排序引入了“标志位”来检测是否需要继续进行下一轮的排序。如果在一次遍历中没有发生任何交换,那么可以确定数列已经有序,此时无需再进行后续的比较。这种方法大大减少了冒泡排序的...

    冒泡排序的算法分析与改进.txt

    ### 冒泡排序的算法分析与改进 #### 冒泡排序基本原理 冒泡排序是一种简单的排序算法,其基本思想是通过重复地遍历要排序的列表,比较每对相邻项目,如果它们的顺序错误(即第一个项目比第二个项目大)就交换它们的...

    冒泡排序改进算法 /鸡尾酒算法

    为了提高冒泡排序的效率,人们提出了多种改进算法,其中鸡尾酒排序(Cocktail Sort,又称双向冒泡排序)是一种常见的优化策略。 鸡尾酒排序的基本思想是在排序过程中,不仅从左向右进行比较和交换,还会从右向左...

    冒泡排序法的面试简历题目

    冒泡排序法是一种基础但重要的排序算法,常用于面试中测试候选人的编程基础。它的工作原理是通过重复遍历待排序的序列,比较相邻元素并根据需要交换它们的位置,使得每一遍过后的最大(或最小)元素“浮”到序列的...

    冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现

    将待排序的序列分为两半,分别对这两半进行排序,然后将排序后的两个子序列合并成一个有序序列。源码实现中,需要递归地进行分治操作,以及一个合并函数来合并两个已排序的子序列。 7. **快速排序**:快速排序由C.A...

    冒泡排序改进版C语言算法实现

    排序是算法的最基本入门,冒泡排序是最简单的一个算法,但是经典的算法却存在累赘冒泡,设置标志变量,可以提高算法效率

    冒泡排序c++源程序

    根据给定的文件信息,我们可以深入探讨冒泡排序算法及其在C++中的实现。冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复...

    c语言数组冒泡排序

    **冒泡排序是一种基础的排序算法...- **双方向冒泡**:改进冒泡排序,同时从两端向中间冒泡,以提高效率。 以上就是关于C语言实现冒泡排序的详细说明,通过理解和实践这些概念,你可以更好地掌握排序算法的基础知识。

Global site tag (gtag.js) - Google Analytics