上一篇文章「 排序算法 」已经整体的把排序算法的分类和评估方法介绍了一下,今天起咱们就开始依次介绍一下各种排序算法的原理和特性。咱们就从最容易理解的「 冒泡排序 」开始吧。
冒泡排序是一种交换排序,它的思路就是在待排序的数据中,两两比较相邻元素的大小,看是否满足大小顺序的要求,如果满足则不动,如果不满足则让它们互换。然后继续与下一个相邻元素的比较,一直到一次遍历完成。一次遍历的过程就被成为一次冒泡,一次冒泡的结束至少会让一个元素移动到了正确的位置。所以要想让所有元素都排序好,一次冒泡还不行,我们得重复N次去冒泡,这样最终就完成了N个数据的排序过程。
通过上面的描述,可以看出来冒泡排序在代码实现层面不就是两层循环嘛,哈哈。
下面举例:
如图,这是针对数组:5,1,4,2,8 采用冒泡排序进行从小到大的排列,上图中分别进行了三次冒泡后完成了整个排序过程。
先看第一次冒泡:
第二次冒泡和第三次冒泡的原理与第一次冒泡一样,这里就不描述了,直接看上图,图中有清晰的流程标注。
我们在写冒泡排序的时候,有两个事项需要注意:
for (int i = 0; i < n; i++) {
// flag是用来标记本次冒泡中是否有元素交换,用来决定冒泡停止条件的
boolean flag = false;
for (int j = 0; j < n-i-1; j++) {
// 从第一个开始,相邻元素两两比较,如果前一个比后一个大则交换
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true; // 如果有元素交换了,就设置为true
}
}
// 一次冒泡下来没有元素交换,就提前退出
if (!flag) break;
}
}
/**
* 从后往前冒泡
*/
public void bubbleSort2(int[] arr, int n) { for (int i = 0; i < n; i++) {
// flag是用来标记本次冒泡中是否有元素交换,用来决定冒泡停止条件的
boolean flag = false;
for (int j = n-i-1; j > i; j--) {
// 从第最后一个开始,相邻元素两两比较,如果前一个比后一个大则交换
if (arr[j-1] > arr[j]) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
flag = true; // 如果有元素交换了,就设置为true
}
}
// 一次冒泡下来没有元素交换,就提前退出
if (!flag) break;
}
}
}
我们按照前一篇文章讲到的排序算法评估方法来对「 冒泡排序 」进行一下评估:
以上,就是对数据结构中「 冒泡排序 」的一些思考,您有什么疑问吗?