本文主要是介绍排序算法-冒泡排序法(BubbleSort),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
排序算法-冒泡排序法(BubbleSort)
1、说明
冒泡排序法又称为交换排序法,是从观察水中的气泡变化构思而成的,原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较,就仿佛气泡从水底逐渐冒升到水面上一样。如此扫描过一次之后就可以确保最后一个元素位于正确的顺序。接着逐步进行第二次扫描,直到完成所有元素的排序为止。
2、算法分析
- 最坏情况和平均情况均需比较:次,时间复杂度为。最好情况只需完成一次扫描,若发现没有进行数据互换位置的操作,则表示已经排序完成,所以只进行了n-1次比较,时间复杂度为。
- 由于冒泡为相邻两个数据相互比较而后决定是否互换位置,并不会改变原来排列的顺序,因此属于稳定排序法。
- 因为只需一个额外的空间,所以空间复杂度为最佳。
- 此排序法适用于数据量小或有部分数据已经过排序的情况。
3、C++代码
第一种案例
#include<iostream>
using namespace std;int main() {int data[6] = { 6,5,9,7,2,8 };cout << "原始数据:" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << " ";}cout << endl;cout << "-----------" << endl;//第1次排序后的结果是://5 6 7 2 8 9//第2次排序后的结果是://5 6 2 7 8 9//第3次排序后的结果是://5 2 6 7 8 9//第4次排序后的结果是://2 5 6 7 8 9//第5次排序后的结果是://2 5 6 7 8 9for (int i = 5; i > 0; i--) {for (int j = 0; j < i; j++) {if (data[j] > data[j + 1]) {int temp = 0;temp = data[j];data[j] = data[j + 1];data[j + 1] = temp;}}cout << endl;}cout << "最终数据:" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << " ";}cout << endl;return 0;
}
输出结果
第二种案例
#include<iostream>
using namespace std;int main() {int data[6] = { 6,5,9,7,2,8 };cout << "原始数据:" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << " ";}cout << endl;cout << "-----------" << endl;//第1次排序后的结果是://5 6 7 2 8 9//第2次排序后的结果是://5 6 2 7 8 9//第3次排序后的结果是://5 2 6 7 8 9//第4次排序后的结果是://2 5 6 7 8 9for (int i = 5; i >= 0; i--) {int flag = 0;for (int j = 0; j < i; j++) {if (data[j] > data[j + 1]) {int temp = 0;temp = data[j];data[j] = data[j + 1];data[j + 1] = temp;flag++;}}if (flag == 0)break;}cout << "最终数据:" << endl;for (int i = 0; i < 6; i++) {cout << data[i] << " ";}return 0;
}
输出结果
这篇关于排序算法-冒泡排序法(BubbleSort)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!