排序算法]史上最简单易懂的 [气泡排序]。
按照套路,先来一通理论层面的陈述:
1、冒泡排序基本思想:
通过对待排序序列从前向后(从下标较小的元素开始),依次对相邻两个元素的值进行两两比较,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就如果水底下的气泡一样逐渐向上冒。
2、先以一个数组讲解一下,然后再写代码:
待排序数组:3,9,-1,10,20
第一轮排序:
(1)3,9,-1,10,20 ----3跟9比较,不交换
(2)3,-1,9,10,20 ----9比 -1大,所以9跟 -1交换
(3)3,-1,9,10,20 ----9跟10比较,不交换
(4)3,-1,9,10,20 ----10跟20比较,不交换
第一轮过后,将20这个最大的元素固定到了最后的位置
第二轮排序:
因为20的位置已经固定,所以只对前4个进行排序即可:
(1)-1,3,9,10,20 ----3比 -1大,进行交换
(2)-1,3,9,10,20 ----3跟9比较,不交换
(3)-1,3,9,10,20 ----9跟10比较,不交换
第二轮过后,将第二大的元素固定到了倒数第二个位置
第三轮排序:
10和20的位置已经确定,只需对前三个进行排序
(1)-1,3,9,10,20 ----3和-1比较,不交换
(2)-1,3,9,10,20 ----3和9比较,不交换
第三轮过后,将第三大的元素位置确定
第四轮排序:
只对前两个元素进行排序
(1)-1,3,9,10,20 ----3和-1比较,不交换
第四轮过后,将第四大的元素位置确定,此时总共5个元素,已经排序好4个,从而最后一个自然而然就是排好序的了
小结:
设总的元素个数为n,那么由上边的排序过程可以看出:
(1)总计需要进行(n-1)轮排序,也就是(n-1)次大循环
(2)每轮排序比较的次数逐轮减少
(3)如果发现在某趟排序中,没有发生一次交换, 可以提前结束冒泡排序。(详见下边优化部分)
3、代码实现部分:
首先按照上边讲解的分步递推,代码如下:
//待排序数组
int[] arr = {3, 9, -1, 10, 20};
int temp;//用于交换时使用
//总共5个数据,因此只需要排序4趟就可以完成
//因为总共5个数据,其中4个排好序之后,最后一个就自然就有位置了
//第一轮,5个数据共进行4次两两比较,所以为arr.length-1,确定出最大的数放到最后的位置
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//第二轮,因为第一轮已经确定出最大的数并放到了最后位置
//因此,第二轮只需要对前边的4个数进行排序
//而4个数需要进行3次两两比较,所以是arr.length-1-1
for (int j = 0; j < arr.length - 1 - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//第三轮,只对前边3个数据进行排序,所以为arr.length-1-2
for (int j = 0; j < arr.length - 1 - 2; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//第四轮
for (int j = 0; j < arr.length - 1 - 3; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
通过这样的分步递推,因此我们可以写成循环的形式,代码如下:
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
4、优化部分:
通过上边讲解的例子,我们也可以看出从第二轮过后,其实数组已经是有序的了,但是按照算法步骤来走的话,即使已经排好序了,但仍是会进行后边的比较,知道全部比较完成
因此,我们可以对代码进行优化,如果发现在某趟排序中,没有发生一次交换, 可以提前结束冒泡排序。
解决方式:可以通过一个标志位来进行判断
具体代码如下:
//定义一个标志位,用于判定元素之间是否进行了交换
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
//进入这个if分支里边,则说明有元素进行了交换
//所以将flag=true
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
//在进行完一轮的排序之后,判断本轮是否发生了元素之间的交换
//如果没有发生交换,说明数组已经是有序的了,则直接结束排序
if (!flag) {
break;
} else {
//如果发生了交换,那么在下一轮排序之前将flag再次置为false
//以便记录下一轮排序的时候是否会发生交换
flag = false;
}
}
欧了,到这我想应该及解释的足够详细了,我是小K,勇敢做自己,做最好的自己=。
推荐阅读
-
气泡排序(超级详细)--升序",从小到大;另一种是 "降序",从大到小。该主题可抽象为 "按升序对 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 次比较。
-
[排序算法] - 气泡排序的三种实现(Java)
-
排序算法 (I) - 用气泡法进行排序的算法
-
气泡排序的经典算法(简略版)
-
气泡排序算法的详细分析
-
十大排序算法讲解(一)气泡排序、选择排序、插入排序、快速排序、希尔排序 [简单易懂]
-
排序算法]史上最简单易懂的 [气泡排序]。
-
排序算法:气泡排序(改进版)的思路分析和代码实现
-
[排序算法] 气泡排序(改进版)的思路分析和代码实现细节 - 二次行程排序:
-
排序算法 - 气泡排序的原理和代码实现