常用12大排序算法之四:交换排序之冒泡排序

2017-04-22 17:08 阅读 1,347 次 评论 0 条

1.冒泡排序的基本思想

交换排序的基本思想是:两两比较待排序记录(数据表)的关键字(排序码),发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。主要包括冒泡排序和快速排序。

冒泡排序容易理解,因为就像泡泡一样,最轻的率先“冒”出来占据第一的位置,随后是剩下的最轻的再冒出来,占据第二的位置,就这样一步步冒出来,也就完成了排序。

 

2.冒泡排序的步骤

(1)冒泡排序算法的运作如下:

a.对象个数n。最多作最多作n-1趟, i= 0, 2, …, n-1 。

b.第i趟中从后向前j= n-1, n-2, ……, i,顺次两两比较。

c.比较如果发生逆序,则交换V[j-1] 和V[j]。

冒泡排序算法

(2)例子:以对 3  2  4  1 进行冒泡排序说明

第一轮 排序过程

3  2  4  1    (最初)

2  3  4  2    (比较3和2,交换)

2  3  4  1    (比较3和4,不交换)

2  3  1  4    (比较4和1,交换)

第一轮结束,最大的数4已经在最后面,因此第二轮排序只需要对前面三个数进行再比较。

第二轮 排序过程

2  3  1  4 (第一轮排序结果)

2  3  1  4 (比较2和3,不交换)

2  1  3  4 (比较3和1,交换

第二轮结束,第二大的数已经排在倒数第二个位置,所以第三轮只需要比较前两个元素。

第三轮 排序过程

2  1  3  4  (第二轮排序结果)

1  2  3  4  (比较2和1,交换)

至此,排序结束。

总之就是每一趟都是将剩余中最大或最小的数据项排在前面已经“冒”出来的数据表后面,遍历完毕也就实现了排序。

 

3.冒泡排序分析

(1)最好情况:正序排列,比较次数(KCN):n−1 ; 移动次数(RMN):为0。则对应的时间复杂度为O(n)。

完全正序排列的话,只需一趟就能判定是否有序,如果遍历j之后发现没有发生逆序就说明已经有序,所以,共比较了n−1次,移动0次。

(2)最坏情况:逆序排序,比较次数(KCN): n(n−1)/2;移动次数(RMN): n(n−1)/2。
完全逆序排序的话,第i都要比较n−i次,而每次比较都要移动3次数据项来交换记录位置。因此总的时间复杂度为O(n2)。

(3)冒泡排序算法,需要一个附加空间,是一个稳定的排序算法

 

4.冒泡排序算法C语言源代码

 

5.冒泡排序算法C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之四:交换排序之冒泡排序 | 算法君

发表评论


表情