经典算法—冒泡排序

经典算法—冒泡排序原文链接:冒泡排序-经典排序算法|逍遥游冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序算法。算法原理冒泡排序的原理(以递增序为例)是每次从头开始依次比较相邻的两个元素,如果后面一个元素比前一个要大,说明顺序不对,则将它们交换,本次循环完毕之后再次从…

经典算法---冒泡排序"

原文链接: 冒泡排序—经典排序算法 | 逍遥游

 

冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换,一些元素慢慢被换到最后,看起来就像是元素在冒泡一样”而得名,是一种简单的基于关键词比较的排序算法。

 

算法原理

冒泡排序的原理(以递增序为例)是每次从头开始依次比较相邻的两个元素,如果后面一个元素比前一个要大,说明顺序不对,则将它们交换,本次循环完毕之后再次从头开始扫描,直到某次扫描中没有元素交换,说明每个元素都不比它后面的元素大,至此排序完成。

由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。

 

时间复杂度

若文件的初始状态是排好序的的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数 M 均达到最小值(Cmin = n-1、Mmin = 0)

所以,冒泡排序最好的时间复杂度为O(N)。

  若初始文件是反序的,需要进行N趟排序。每趟排序要进行 C = N-1次关键字的比较(1≤i≤N-1)和总共(Mmax = (N*(N-1))/2)次的移动(移动次数由乱序对的个数决定,即多少对元素顺序不对,如 1 3 4 2 5 中共有(3,2)、(4,2)两个乱序对),在这种情况下,比较和移动次数均达到最大值(Cmax =N*(N-1) + Mmax=(N*(N-1))/2 = O(N^2))。所以,冒泡排序的最坏时间复杂度为O(N^2)

 

综上,冒泡排序总的平均时间复杂度为O(N^2)。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。如果两个相等的元素相邻,那么根据我们的算法。它们之间没有发生交换;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

 

算法改进

由于冒泡排序算法还是比较慢的,所以有很多人对在此基础上进行了改进,我只简单介绍一下我所知道的。

第一种是上浮操作与下沉操作相结合。传统的冒泡排序只有上浮操作,如果碰到一些很特殊的数据就会显得笨一点,例如(2、3、4、5、1)这个数列按增序排列,那么按照普通冒泡算法就要扫描5趟,可是我们一眼就看出来直接把 1 挪到第一个就行了,扫描 5 次实在是太笨了,于是我们在每次上浮操作后加上一个下沉操作,这样就更快了。

第二中改进是减少无效比较的次数。所谓无效比较就是当我们已知结果却还要去比较。如果我们多观察冒泡排序的中间过程,我们就会发现,末尾的一些元素在一定次数的扫描后已经到达最终位置了(因为每次扫描后都至少会有一个新的元素到达最终位置),再比较就会造成无效比较。改进方法是,记录下每次扫描中发生交换的最后一个元素位置,下一次扫描就到这里为止。

可是,无论怎么改进,冒泡排序的时间复杂度都是O(N^2)。

 

下面给出冒泡排序的C++参考代码和下载地址。

 

 

//冒泡排序部分,参数形式与标准库的快排一样

//ps:(point start)所需排序的数据首地址

//pe:(point end)  所需排序的数据第一个无效地址

//cmp:自定义的比较函数

int sort(int *ps,int *pe,bool(*cmp)(int,int))

{

//用以判断某次循环后是否有元素位置发生变化

    bool flag=true;

 

    while(flag)

    {

        flag=false;//假设没有交换

 

        //上浮过程

        for(int i=1;i<pe-ps;i++)//注意:i从1开始

        {

            if(cmp(ps[i],ps[i-1]))

            {

                swap(ps[i],ps[i-1]);

                flag=true;//有元素发生交换,说明排序可能没有结束

            }

        }

    }

    return 0;

}

 

 

 

 

更详细的代码,请点击这里下载。

 

来源:逍遥游,欢迎分享本文,转载请保留出处!

今天的文章经典算法—冒泡排序分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/34034.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注