【排序算法】史上最通俗易懂的【冒泡排序】详解 |
您所在的位置:网站首页 › 排序的使用条件 › 【排序算法】史上最通俗易懂的【冒泡排序】详解 |
按照套路,先来一通理论层面的陈述: 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,勇敢做自己,做最好的自己=。
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |