冒泡排序(BubbleSort)
2024-10-10 10:22:21
介绍:
冒泡排序是一种最基础的交换排序(两两比较待排序的关键字,交换不满足次序要求的那对数,直到整个表都满足次序要求为止),工作方式如同碳酸饮料中的二氧化碳气泡最终会上浮到顶端一样,故名"冒泡排序"。
算法描述:
一次比较相邻的数据,将小数据放在前(假设非递减排列),大数据放在后。即第一趟比较第n个和第n-1个数,小数在前,大数在后,再比较第n-1个数与第n-2个数,小数在前,大数在后,以此类推比较第1个和第0个数,小数在前,大数在后;第一趟后最小元素已放在正确位置,以此类推,直到全部元素放在正确的位置。
性能分析:
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定
代码实现:
// Java代码
class BubbleSort {
public static void bubbleSort(int[] a) {
// i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
// 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
for (int i = 0; i < a.length - 1; ++i) {
// 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
for (int j = a.length - 1; j > i; --j) {
if (a[j] < a[j - 1]) {// 交换不满足次序要求的元素
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}
}
// C++代码
class BubbleSort {
public:
static void bubbleSort(int a[], int length) {
// i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
// 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
for (int i = 0; i < length - 1; ++i) {
// 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
for (int j = length - 1; j > i; --j) {
if (a[j] < a[j - 1]) {// 交换不满足次序要求的元素
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}
};
算法优化:
考虑一些特殊情况,比如:
(1)待排序序列已经有序,整个代码任然会执行无效的遍历和比较。
(2)数据已经排好序,但任然会进行下一轮比较,直到length-1次,后面的比较都是无意义的。
可以通过设置标志位flag,如果发生了交换就改变flag设置为true,如果没有交换就保持false。当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。退出循环,排序完成。
// Java代码
class BubbleSort {
public static void bubbleSort2(int[] a) {
boolean flag = false;// 标记第i趟是否发生元素交换
// i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
// 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
for (int i = 0; i < a.length - 1; ++i) {
flag = false;// 每趟默认未进行元素交换
// 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
for (int j = a.length - 1; j > i; --j) {
if (a[j] < a[j - 1]) {// 交换不满足次序要求的元素
flag = true;// 发生元素交换,改变flag
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
if (flag == false) {// 未发生交换,序列满足要求,完成排序
break;// 跳出循环
}
}
}
}
// C++代码
class BubbleSort {
public:
static void bubbleSort2(int a[], int length) {
bool flag = false;// 标记第i趟是否发生元素交换
// i表示这一趟要填入正确元素的位置,最后一个位置不需要比较
// 因为n-1个元素在正确位置,最后一个位置自然填入正确元素
for (int i = 0; i < length - 1; ++i) {
flag = false;// 每趟默认未进行元素交换
// 从后往前依次比较,将最小元素"冒泡"到最前方,要填入正确元素的位置i
for (int j = length - 1; j > i; --j) {
if (a[j] < a[j - 1]) {// 交换不满足次序要求的元素
flag = true;// 发生元素交换,改变flag
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
if (flag == false) {// 未发生交换,序列满足要求,完成排序
break;// 跳出循环
}
}
}
};
最新文章
- 在MyEclipse显示struts2源码和doc文档及自动完成功能
- STL中list和vector在添加元素时push_back会调用拷贝构造函数
- 设计模式之美:State(状态)
- JS设置CSS样式的几种方式【转】
- 剑指Offer:面试题27——二叉搜索树与双向链表(java实现)
- rpc rmi http
- python笔记 - day7
- android138 360 小火箭
- UVA 10041 Vito&#39;s Family (中位数)
- 类模板 template<;class T>;
- PTA 07-图4 哈利&#183;波特的考试 (25分)
- Java包详解
- 自动测试工具SilkTest全面介绍
- Dom解析xml源代码
- 第十篇 一个利用反射实现的Excel导出
- Selenium 2.0与Selenum 3.0介绍
- 机器学习实验一SVM分类实验
- RestTemplate发送请求并携带header信息 RestTemplate post json格式带header信息
- python日期加减法操作
- 微软Azure AspNetCore微服务实战 第一期