冒泡排序,真的很简单,不是嘛,如果给你15分钟,也许你会很快就写出来一个,真的,我相信你,而且说不定考虑的还是相当周全滴,在此仅以此博客记录一下,我所认识的冒泡排序。
冒泡排序,为什么取这个名?
你可以想想池塘里的气泡,从最底部向最上部浮起的过程,是不是由小变大的过程中,这是一个物理知识,就不用说了吧,不知道的,回去看看初中科本吧,因此浮到水面的气泡是不是最大的,这也就是取名冒泡的原因啦,浮到最上面的就是最大的,当然你别认为冒泡只能实现从小到大排序,大与小本身就是一种相对概念~
冒泡排序的思路(从小到大排序)
1:比较相邻的元素,如果第一个元素比第二个元素小,就将其交换之
2:对每一对相邻元素都做同样的工作,从第一对直至最后一对
3:做完第2步,这里最大的元素已经浮至最上面的位置,去除最后一个元素,重新执行上面的步骤,如果所有相邻元素的比较过程中均没有交换发生,排序完成。
冒泡排序的时间复杂度
最好的情况下,是待排序的元素已经处于有序的状态,这里只需要n-1次比较就可以了,也不需要进行元素的交换,因此最好时间复杂度为O(n)
最坏的情况下,是待排序的元素处于逆序的状态,因此每次循环都需要进行n-i-1次比较,根据数学知识(高中的)可以得知总共需要的比较次数是n*(n-1)/2,对于每次的比软均需要3次移动交换操作,因此总共的移动交换操作数为3n*(n-1)/2.因此总共的时间复杂度为O(n^2)
因此算法的平均时间复杂度为O(n^2)
冒泡排序的空间复杂度
空间复杂度这个很好计算,看一眼就知道了吧,整个程序中就用到了一个变量,用于交换用,因此空间复杂度为O(1),但是不一定呦,下面有程序二将空间复杂度降为0
冒泡排序的稳定性
稳定性,这个也是显然的,是稳定的,两个相邻元素,如果是相等的,就不进行交换,除非是你有意为之~~~
普通的冒泡排序源程序
void BubbleSort(int *a ,int N)
{
bool flag=true;
int tmp;
for(int i=0;i<N;i++)
{
for(int j=0;j<N-i;j++)
{
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
flag=false;
}
}
if(flag)
break;
}
return ;
}
更快的空间复杂度为0的冒泡排序
void BubbleSort(int *a ,int N)
{
bool flag=true;
for(int i=0;i<N;i++)
{
for(int j=0;j<N-i;j++)
{
if(a[j]>a[j+1])
{
a[j]=a[j]^a[j+1];
a[j+1]=a[j+1]^a[j];
a[j]=a[j+1]^a[j];
flag=false;
}
}
if(flag)
break;
}
return ;
}
上面代码用到了异或操作,降低算法空间复杂度
分享到:
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
利用VB编程,最简单的冒泡排序代码 冒泡排序(Bubble Sort)是在一列数据中把较小的数据逐次向上推移的一种排序技术。冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据,从最下面的一个元素起,...
1.冒泡排序的原理:每次都从第一个元素开始(索引0),向后两两比较,只要后面的比前面的大,就交换(从大到小) 2.通过画图分析,5个数字排4趟,n数字排n-1趟,而外层的for循环代表的是循环的趟数,所以外层循环的结束条件是...
完整的程序,代码简介,便于理解,适合于初学者。
arm汇编写的冒泡排序算法,简单易懂,最基本的arm汇编应用。
试通过随机数据比较快速排序、起泡排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;... (3)对冒泡排序应指出进行了多少趟。
冒泡排序,作为最基本的排序算法,由于原理像冒泡一样,所以取名为冒泡排序; 我们知道,水泡在上升时,总是密度最小的最先上去,假如一个水层只能容纳一个水泡,那么水泡由上到下的排序就是密度逐渐增大的排序。...
在众多排序算法中,冒泡排序是最基础和最简单的一种。 冒泡排序的基本思想是通过不断比较相邻元素并交换它们的位置,使得较大的元素逐渐“浮”到数组的末端。这个过程会不断重复,直到整个数组都有序为止。虽然冒泡...
排序是算法的最基本入门,冒泡排序是最简单的一个算法,但是经典的算法却存在累赘冒泡,设置标志变量,可以提高算法效率
冒泡排序是一种简单的排序算法,它的基本思想是通过对待...效率问题:尽管冒泡排序概念上简单易懂,但它并不是最高效的排序算法,特别是对于大型数据集。它的平均和最坏情况时间复杂度均为O(n²),其中n是列表的长度。
冒泡,快速排序算法比较试分别实现冒泡排序和非递归形式的快速排序算法,并通过随机数据比较两种排序算法中关键字的比较次数和移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少...
因此,对于大规模数据的排序,冒泡排序可能并不是最高效的选择。然而,由于其实现简单,对于小规模数据或者部分有序的数据,冒泡排序仍然具有一定的实用价值。 值得注意的是,冒泡排序是一种稳定的排序算法,即相等...
最简单的,我看网上的有点不清晰,自己就做出来,存到这里,电脑就不用存了,可以当储存的地方放了
Python冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。这个过程会对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,...
冒泡排序(最好是O(n), 最坏O(n2)) 原理: 拿自己与上面一个比较,如果上面一个比自己小就将自己和上面一个调换位置,依次再与上面一个比较,第一轮结束后最上面那个一定是最大的数 冒泡排序代码 def bubble_sort...
冒泡排序是一种简单的排序算法,它的基本思想是通过相邻元素之间的比较和交换,将待排序序列中的最大元素逐步沉底,直到整个序列有序为止。冒泡排序的时间复杂度为O(n^2),其中n为待排序序列的长度。 冒泡排序的...
冒泡排序是一种简单的排序算法,其原理是多次循环比较相邻的元素,并依次交换位置,从而将最大(或最小)的元素逐渐“冒泡”到数组的最后。具体步骤如下: 1. 从数组的第一个元素开始,通过比较相邻的两个元素,...
冒泡排序是一种简单但效率较低的排序算法,它通过比较相邻元素并交换它们的位置,逐步将最大值“冒泡”到数组的末尾。在这个教程中,我们将深入研究冒泡排序的原理,并提供一个Java示例来演示如何实现它。不管您是...
附件是Python 版冒泡排序算法源代码,文件...冒泡排序的时间复杂度为O(n^2),在最坏的情况下(即数组完全逆序)需要进行n*(n-1)/2次比较。尽管这不是一个效率很高的排序算法,但由于其实现简单,常被用来作为教学目的。