好程序员Java学习路线分享冒泡排序及优化
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了好程序员Java学习路线分享冒泡排序及优化,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含10321字,纯文字阅读大概需要15分钟。
内容图文
? 好程序员Java学习路线分享冒泡排序及优化,冒泡排序是一定典型的交换排序,如排序规则是升序,有如下数列:? A[0] A[1] A[2] A[3] ...... A[n]
? 将A[0]和A[1]比较,如果A[0]>A[1] ,则交换两个元素的位置,否则不变, 再继续比较A[1]和A[2],直到A[n-1]和A[n]。即比较相邻的两个元素,如果前一个大,就交换(否则不交换),再继续比较后面的元素,每一轮比较之后,最大的元素会移动到最后(完成一轮冒泡);再开始第二轮冒泡,本次会选出第二大的元素。重复冒泡的过程,直到没有相邻的元素需要交换,则排序完成,像碳酸饮料中的气泡,故而称为冒泡排序。
???
简化过程,设置一个简单的数组,在编程中,元素的索引从0开始:
[5, 3, 1, 4, 2]
????int[] nums = {5, 3, 1, 4, 2};
????//要比较n次,n是数组中数字的个数
????for (int i = 0; i < nums.length; i++) {
????????//比较j和j+1位置的元素,每比较完一次,最大的元素会移动到末尾
????????for (int j = 0; j < nums.length - 1; j++) {
????????????if (nums[j] > nums[j + 1]) {
????????????????int temp = nums[j + 1];
????????????????nums[j + 1] = nums[j];
????????????????nums[j] = temp;
????????????}
????????}
????}
第一轮比较,经过这一轮比较,最大的元素在末尾
[<font color="red">5, 3</font>, 1, 4, 2] 比较第0和1个元素 ,交换 [<font color="red">3, 5</font>, 1, 4, 2]<br/>
[3,<font color="red"> 5, 1</font>, 4, 2] 比较第1和2个元素 ,交换 [3, <font color="red">1, 5</font>, 4, 2]<br/>
[3, 1, <font color="red">5, 4</font>, 2] 比较第2和3个元素 ,交换 [3,1, <font color="red"> 4, 5</font>, 2]<br/>
[3, 1, 4, <font color="red">5, 2</font>] 比较第3和4个元素 ,交换 [3, 1, 4, <font color="red">2, 5</font>] 最大的元素在末尾<br/>
第二轮比较,经过这轮比较,最大的两个元素在末尾
[<font color="red">3, 1</font>, 4, 2, 5] 比较第0和1个元素 ,交换 [<font color="red">1, 3</font>, 4, 2, 5]<br/>
[1, <font color="red">3, 4</font>, 2, 5] 比较第1和2个元素 ,不动 [1, <font color="red">3, 4</font>, 2, 5]<br/>
[1, 3, <font color="red">4, 2</font>, 5] 比较第2和3个元素 ,交换 [1, 3, <font color="red">2, 4</font>, 5]<br/>
[1, 3, 2, <font color="red">4, 5</font>] 比较第3和4个元素 ,不动 [1, 3, 2, <font color="red">4, 5</font>] ?这次比较是多余的,因为第1轮过后,最大的元素在末尾<br/>
第三轮比较,经过这轮比较,最大的三个元素在末尾
[<font color="red">1, 3</font>, 2, 4, 5] 比较第0和1个元素 ,不动 [<font color="red">1, 3</font>, 2, 4, 5]<br/>
[1, <font color="red">3, 2</font>, 4, 5] 比较第1和2个元素 ,交换 [1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, 2,<font color="red"> 3, 4</font>, 5] 比较第2和3个元素 ,不动 [1, 2, <font color="red">3, 4</font>, 5] ?这次比较多余的<br/>
[1, 2, 3, <font color="red">4, 5</font>] 比较第3和4个元素 ,不动 [1, 2, 3, <font color="red">4, 5</font>] ?这次比较是多余的<br/>
第四轮比较,经过这轮比较,最大的四个元素在末尾
[<font color="red">1, 2</font>, 3, 4, 5] 比较第0和1个元素 ,不动 [<font color="red">1, 2</font>, 3, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5] 比较第1和2个元素 ,不动 [1, <font color="red">2, 3</font>, 4, 5] ?这次比较是多余的<br/>
[1, 2,<font color="red"> 3, 4</font>, 5] 比较第2和3个元素 ,不动 [1, 2, <font color="red">3, 4</font>, 5] ?这次比较是多余的<br/>
[1, 2, 3, <font color="red">4, 5</font>] 比较第3和4个元素 ,不动 [1, 2, 3, <font color="red">4, 5</font>] ?这次比较是多余的<br/>
第五轮比较,经过这轮比较,排序完成
[<font color="red">1, 2</font>, 3, 4, 5] 比较第0和1个元素 ,不动 [<font color="red">1, 2</font>, 3, 4, 5] ?这次比较是多余的<br/>
[1, <font color="red">2, 3</font>, 4, 5] 比较第1和2个元素 ,不动 [1, <font color="red">2, 3</font>, 4, 5] ?这次比较是多余的<br/>
[1, 2, <font color="red">3, 4</font>, 5] 比较第2和3个元素 ,不动 [1, 2, <font color="red">3, 4</font>, 5] ?这次比较是多余的<br/>
[1, 2, 3, <font color="red">4, 5</font>] 比较第3和4个元素 ,不动 [1, 2, 3, <font color="red">4, 5</font>] ?这次比较是多余的<br/>
可以看到冒泡排序每次都从头比较,比较到末尾,但实际
第一轮比较后,最后1个数是最大的,下一轮不需要参与比较
第二轮比较后,最后2个数是最大的,下一轮不需要参与比较
第三轮比较后,最后3个数是最大的...
所以第n轮比较的时候,可以排除掉末尾已经排序好的元素,即末尾n-1个元素
int[] nums = {5, 3, 1, 4, 2};
????????//要比较n次,n是数组中数字的个数
????????for (int i = 0; i < nums.length; i++) {
????????????//比较j和j+1位置的元素,每比较完一次,最大的元素会移动到末尾
????????????//最后i个元素不参与本次比较
????????????for (int j = 0; j < nums.length - 1 - i; j++) {
????????????????if (nums[j] > nums[j + 1]) {
????????????????????int temp = nums[j + 1];
????????????????????nums[j + 1] = nums[j];
????????????????????nums[j] = temp;
????????????????}
????????????}
????????}
运行结果:
第一轮比较,经过这一轮比较,最大的元素在末尾
[<font color="red">5, 3</font>, 1, 4, 2] 比较第0和1个元素 ,交换 [<font color="red">3, 5</font>, 1, 4, 2]<br/>
[3,<font color="red"> 5, 1</font>, 4, 2] 比较第1和2个元素 ,交换 [3, <font color="red">1, 5</font>, 4, 2]<br/>
[3, 1, <font color="red">5, 4</font>, 2] 比较第2和3个元素 ,交换 [3,1, <font color="red"> 4, 5</font>, 2]<br/>
[3, 1, 4, <font color="red">5, 2</font>] 比较第3和4个元素 ,交换 [3, 1, 4, <font color="red">2, 5</font>] 最大的元素在末尾<br/>
第二轮比较,经过这轮比较,最大的两个元素在末尾
[<font color="red">3, 1</font>, 4, 2, 5] 比较第0和1个元素 ,交换 [<font color="red">1, 3</font>, 4, 2, 5]<br/>
[1, <font color="red">3, 4</font>, 2, 5] 比较第1和2个元素 ,不动 [1, <font color="red">3, 4</font>, 2, 5]<br/>
[1, 3, <font color="red">4, 2</font>, 5] 比较第2和3个元素 ,交换 [1, 3, <font color="red">2, 4</font>, 5]<br/>
第三轮比较,经过这轮比较,最大的三个元素在末尾
[<font color="red">1, 3</font>, 2, 4, 5] 比较第0和1个元素 ,不动 [<font color="red">1, 3</font>, 2, 4, 5]<br/>
[1, <font color="red">3, 2</font>, 4, 5] 比较第1和2个元素 ,交换 [1, <font color="red">2, 3</font>, 4, 5]<br/>
第四轮比较,经过这轮比较,最大的四个元素在末尾
[<font color="red">1, 2</font>, 3, 4, 5] 比较第0和1个元素 ,不动 [<font color="red">1, 2</font>, 3, 4, 5]<br/>
上面的算法,可以减少重复比较的次数,比较的次数是固定的。但如果本来数组中的元素就相对有序,则会出现如下状况:
初始数组是:[3, 1, 2, 4, 5]
第一轮
[<font color="red">3, 1</font>, 2, 4, 5]比较第0和1个元素,交换[<font color="red">1, 3</font>, 2, 4, 5]<br/>
[1,<font color="red"> 3, 2</font>, 4, 5]比较第1和2个元素,交换[1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5]比较第2和3个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
[1, 2, <font color="red">3, 4</font>, 5]比较第3和4个元素,不动[1, 2, 3, <font color="red">4, 5</font>]<br/>
第二轮
[<font color="red">1, 2</font>, 3, 4, 5]比较第0和1个元素,不动[<font color="red">1, 2</font>, 3, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5]比较第1和2个元素,不动[1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, 2, <font color="red">3, 4</font>, 5]比较第2和3个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
第三轮
[<font color="red">1, 2</font>, 3, 4, 5]比较第0和1个元素,不动[<font color="red">1, 2</font>, 3, 4, 5]<br/>
[1,<font color="red">2, 3</font>, 4, 5]比较第1和2个元素,不动[1, <font color="red">2, 3</font>, 4, 5]<br/>
第四轮
[<font color="red">1, 2</font>, 3, 4, 5]比较第0和1个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
实际上数组中的元素,开始的时候只有数字3的位置需要移动,其它元素相对都是有序的。当3移动完成后,其它的元素不需要一定。所以在第二轮发现没有任何元素交换之后,就表示排序已经完成,第三轮和第四轮是多余的。
对于冒泡排序的优化,如果某一轮比较中没有发生任何交换,则代表排序已经完成,不需要再进行排序了:
????????int[] nums = {3, 1, 2, 4, 5};
????????boolean flag;//是否交换的标志
????????//要比较n次,n是数组中数字的个数
????????for (int i = 0; i < nums.length; i++) {
????????????// 每次遍历标志位都要先置为false,才能判断后面的元素是否发生了交换
????????????flag = false;
????????????//比较j和j+1位置的元素,每比较完一次,最大的元素会移动到末尾
????????????//最后i个元素不参与本次比较
????????????for (int j = 0; j < nums.length - 1 - i; j++) {
????????????????if (nums[j] > nums[j + 1]) {
????????????????????int temp = nums[j + 1];
????????????????????nums[j + 1] = nums[j];
????????????????????nums[j] = temp;
????????????????????flag = true; ???//表示本轮发生了交换
????????????????}
????????????}
????????????// 如果为false,代表本轮没有交换,元素已经有序
????????????if(!flag) break;
????????}
????}
初始数组是:[3, 1, 2, 4, 5]
第一轮
[<font color="red">3, 1</font>, 2, 4, 5]比较第0和1个元素,交换[<font color="red">1, 3</font>, 2, 4, 5]<br/>
[1,<font color="red"> 3, 2</font>, 4, 5]比较第1和2个元素,交换[1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5]比较第2和3个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
[1, 2, <font color="red">3, 4</font>, 5]比较第3和4个元素,不动[1, 2, 3, <font color="red">4, 5</font>]<br/>
第二轮
[<font color="red">1, 2</font>, 3, 4, 5]比较第0和1个元素,不动[<font color="red">1, 2</font>, 3, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5]比较第1和2个元素,不动[1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, 2, <font color="red">3, 4</font>, 5]比较第2和3个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
在上面的排序中,3是最后一个移动的元素。3之后的元素都是有序的。所以只要比较3之前的元素即可。最后一次发生交换的元素,它后面的元素都是有序的,不需要再参与比较
int[] nums = {3, 1, 2, 4, 5};
????????boolean flag;//是否交换的标志
????????int lastExchangeIndex =0;//最后一次交换的位置
????????int sortBorder = nums.length - 1;
????????//要比较n次,n是数组中数字的个数
????????for (int i = 0; i < nums.length; i++) {
????????????// 每次遍历标志位都要先置为false,才能判断后面的元素是否发生了交换
????????????flag = false;
????????????//比较j和j+1位置的元素,每比较完一次,最大的元素会移动到末尾
????????????//最后i个元素不参与本次比较
????????????for (int j = 0; j < sortBorder ; j++) {
????????????????if (nums[j] > nums[j + 1]) {
????????????????????int temp = nums[j + 1];
????????????????????nums[j + 1] = nums[j];
????????????????????nums[j] = temp;
????????????????????flag = true; ???//表示本轮发生了交换
????????????????????lastExchangeIndex =j;//记录最后一次发生交换的位置
????????????????}
????????????}
????????????// 如果为false,代表本轮没有交换,元素已经有序
????????????sortBorder = lastExchangeIndex;
????????????if(!flag) break;
????????}
运行结果:
第一轮
[<font color="red">3, 1</font>, 2, 4, 5]比较第0和1个元素,交换[<font color="red">1, 3</font>, 2, 4, 5]<br/>
[1,<font color="red"> 3, 2</font>, 4, 5]比较第1和2个元素,交换[1, <font color="red">2, 3</font>, 4, 5]<br/>
[1, <font color="red">2, 3</font>, 4, 5]比较第2和3个元素,不动[1, 2, <font color="red">3, 4</font>, 5]<br/>
[1, 2, <font color="red">3, 4</font>, 5]比较第3和4个元素,不动[1, 2, 3, <font color="red">4, 5</font>]<br/>
第二轮
[<font color="red">1, 2</font>, 3, 4, 5]比较第0和1个元素,不动[<font color="red">1, 2</font>, 3, 4, 5]
原文:https://blog.51cto.com/14479068/2427460
内容总结
以上是互联网集市为您收集整理的好程序员Java学习路线分享冒泡排序及优化全部内容,希望文章能够帮你解决好程序员Java学习路线分享冒泡排序及优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。