【排序算法】史上最通俗易懂的【冒泡排序】详解

2024-06-03 03:09| 来源: 网络整理| 查看: 265

按照套路，先来一通理论层面的陈述：

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，勇敢做自己，做最好的自己=。

【本文地址】

公司简介

联系我们