气泡排序算法的详细分析
首先我们要知道一个前提知识 ,冒泡排序 属于 交换排序 的一种。
那么什么是交换排序?
答:根据序列中两个关键字的大小的比较结果来决定是否交换这两个记录在序列中的位置。
冒泡排序的思想: 1.当我们拿到一个混乱无序的序列的时候,我们可以从前往后依次两两比较相邻元素的值。这里我们假定想要序列从小到大排列。那么每次对比 a[i-1] 与 a[i],若a[i-1] > a[i] 。那么我们就交换这两个元素的位置。
原序列:2 5 4 3 1
对比 2 < 5 不做处理
对比 5 > 4 交换,此时序列:2 4 5 3 1
对比 5 > 3 交换,此时序列:2 4 3 5 1
对比 5 > 1 交换,此时序列:2 4 3 1 5
一轮对比结束,最大元素已经排列到最后,即正确位置。
2.经过一轮的对比,我们是不是把序列中最大的元素放到了最后呢?答案是肯定的!我们形象的理解,就是跟鱼儿吐泡泡一样,慢慢浮出水面,泡泡越来越大。
3.那么我们思考是不是多进行几次就可以实现有序了?emmm,你可能会说:最后一个是有序的,那么我们只需要对前n-1个元素进行处理。对!仔细思考其实我们每一轮都会使得一个元素有序,所以每一轮我们要处理的序列长度都会减一。
4.那么我们一共需要进行几轮呢?
还拿上面的这个序列来说明
原序列:2 5 4 3 1
第一轮结束:2 4 3 1 5 要处理序列变为:2 4 3 1
第二轮结束:2 3 1 4 要处理的序列为:2 3 1
第三轮结束: 2 1 3 要处理序列变为:2 1
第四轮结束:1 2 此时所有序列为 1 2 3 4 5 有序
所以我们可以很直观的得出:我们一共需要n-1轮。而这个n-1轮是最坏的情况。大家可以动手试试 1 5 4 3 2 这个序列,他在第三轮的时候就已经完全有序了。
那么算法思路有了,写code也很简单了
void maopao_sort(int a[],int n){//我们传入数组a[]和元素个数n
for(int i=0;i<n-1;i++){//一共最多进行n-1轮对比
for(int j=0;j<n-1-i;j++){//每一轮我们需要对比的序列长度减一
if(a[j] > a[j+1]) swap(a[j],a[j+1]);//交换
}
}
}
因为最多进行n-1轮,所以我们还可以加一个flag来判断当前是否发生交换从而减少循环量。这里不在赘述。
时间复杂度分析: 最坏循环 n-1 轮,每轮需要进行对比 n - i次。进行求和有 : n(n-1)/2。所以为一种O(n*n)的复杂度。
稳定性分析:因为i > j 且 a[i] = a[j],不会发生交换,所以为一种稳定的排序算法。
上一篇: 经典气泡排序和优化气泡排序法
下一篇: [数据结构] 八排序的泡排序算法
推荐阅读
-
以史为鉴:排序算法的新见解
-
探索 Java 世界中的七种排序算法(上) - 希尔排序(收缩递增排序)
-
什么是冒泡算法?详细解释排序冒泡的原理?用 C 语言实现冒泡算法。
-
气泡排序算法,C 语言气泡排序算法说明
-
算法概览 - "气泡排序
-
气泡排序的 C++ 实现
-
Java 中的经典算法冒泡排序(Bubble Sort)
-
算法]气泡排序
-
气泡排序(超级详细)--升序",从小到大;另一种是 "降序",从大到小。该主题可抽象为 "按升序对 n 个数字排序 "的一般形式。 排序是一种重要的基本算法。排序的方法有很多种,但在本题中我们将使用冒泡排序法。 冒泡法的基本思想 冒泡法的基本思想是,每次比较相邻的两个数字时,较小的那个会被移到前面。如果有 5 个数字9,8,5,2,0,第一次将前两个数字 8 和 9 互换。第二次将第二个和第三个数字(9 和 5)对调......这样一共对调 4 次,得到 8-5-2-0-9 的顺序,可以看到:最大的数字 9 一直在 "下沉",成为最下面的一个数字,而小的数字 "上升" 最小的数字 "上升"。最小的数字 0 已经向上 "浮 "了一个位置。经过第一次比较(共 4 次比较和交换),得到了最大的数字 9。 然后进行第二趟比较,对剩下的前 4 个数字(8、5、2、0)进行新一轮比较,这样第二个最大的数字就 "沉到了底部"。同样,按照上述方法进行第二轮比较。经过 3 次比较和交换,我们得到了第二大数 8。 按照这个规律,我们可以推断出,比较 5 个数字需要 4 次旅行,才能将 5 个数字从小到大排列起来。在第一次旅行中,两个数字之间进行了 4 次比较,在第二次旅行中,进行了 3 次比较......在第四次旅行中,只进行了一次比较。 思路总结 总结:如果有 n 个数字,那么要进行 n-1 次比较。在第一次行程中进行 n-1 次比较,在第 i 次行程中进行 n-i 次比较。
-
C 语言版冒泡排序算法详解 - 三、C 程序的冒泡排序算法