1.冒泡排序
基本介绍:
冒泡排序的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),一次比较相邻元素的值,如果发现逆序,使较大的元素逐渐从前向后移动。
因为在排序的过程中,各元素不断的接近自己的位置,如果一趟比较下来没有进行任何交换,就说明序列有序。因此要在排序过程中设置一个标志flag,判断元素是否进行交换,从而减少不必要的比较。(后期优化)
示例:
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {11,3, 9, -1, 10, -2};
int count=0;
//冒泡排序
//第一层for循环是循环次数:例如5个数,总共循环5-1=4次
System.out.println("原始数据: "+Arrays.toString(arr));
System.out.println("开始排序------");
for (int i = 0; i < arr.length - 1; i++) {
//第二层for循环,是比较次数
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int num=arr[j];
arr[j]=arr[j+1];
arr[j+1] = num;
}
System.out.println("第"+(count++)+"次排序:"+Arrays.toString( arr));
}
System.out.println("内层排序结束---");
}
}
}
输出:
原始数据: [11, 3, 9, -1, 10, -2]
开始排序------
第0次排序:[3, 11, 9, -1, 10, -2]
第1次排序:[3, 9, 11, -1, 10, -2]
第2次排序:[3, 9, -1, 11, 10, -2]
第3次排序:[3, 9, -1, 10, 11, -2]
第4次排序:[3, 9, -1, 10, -2, 11]
内层排序结束---
第5次排序:[3, 9, -1, 10, -2, 11]
第6次排序:[3, -1, 9, 10, -2, 11]
第7次排序:[3, -1, 9, 10, -2, 11]
第8次排序:[3, -1, 9, -2, 10, 11]
内层排序结束---
第9次排序:[-1, 3, 9, -2, 10, 11]
第10次排序:[-1, 3, 9, -2, 10, 11]
第11次排序:[-1, 3, -2, 9, 10, 11]
内层排序结束---
第12次排序:[-1, 3, -2, 9, 10, 11]
第13次排序:[-1, -2, 3, 9, 10, 11]
内层排序结束---
第14次排序:[-2, -1, 3, 9, 10, 11]
内层排序结束---
结论:发现每次排序都会把最大数放在结尾处!
优化,先看案例:
如果给int arr[] = {1, 2, 3, 5, 4}排序呢
输出:
原始数据: [1, 2, 3, 5, 4]
开始排序------
第0次排序:[1, 2, 3, 5, 4]
第1次排序:[1, 2, 3, 5, 4]
第2次排序:[1, 2, 3, 5, 4]
第3次排序:[1, 2, 3, 4, 5]
内层排序结束---
第4次排序:[1, 2, 3, 4, 5]
第5次排序:[1, 2, 3, 4, 5]
第6次排序:[1, 2, 3, 4, 5]
内层排序结束---
第7次排序:[1, 2, 3, 4, 5]
第8次排序:[1, 2, 3, 4, 5]
内层排序结束---
第9次排序:[1, 2, 3, 4, 5]
内层排序结束---
发现3-9次的排序均一样的,这就是优化的点!
public static void main(String[] args) {
int arr[] = {1, 2, 3, 5, 4};
int count = 0;
//冒泡排序
//第一层for循环是循环次数:例如5个数,总共循环5-1=4次
System.out.println("原始数据: " + Arrays.toString(arr));
System.out.println("开始排序------");
//重点1:表示是否进行过交换
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
//第二层for循环,是比较次数
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int num = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = num;
//重点2:如果发生交换,该字段置为true;
flag = true;
}
System.out.println("第" + (count++) + "次排序:" + Arrays.toString(arr));
}
//内层排序结束后,判断这个字段
//没有进行过交换,直接退出!
if (!flag) {
break;
} else {
//flag=true:进行过交换,这里需要重置下flag,方便下次判断!
flag = false;
}
System.out.println("内层排序结束---");
}
}
输出:发现减少了3次排序
原始数据: [1, 2, 3, 5, 4]
开始排序------
第0次排序:[1, 2, 3, 5, 4]
第1次排序:[1, 2, 3, 5, 4]
第2次排序:[1, 2, 3, 5, 4]
第3次排序:[1, 2, 3, 4, 5]
内层排序结束---
第4次排序:[1, 2, 3, 4, 5]
第5次排序:[1, 2, 3, 4, 5]
第6次排序:[1, 2, 3, 4, 5]
内层排序无法减少,即3-6的排序是无法精简的,因为内层排序是元素一位一位去比较,根本不知道后面元素的大小,两次比较结果相同,并不能说明已经有序:如
本以为这么修改:
//上次排序结果
String str="";
for (int i = 0; i < arr.length - 1; i++) {
//第二层for循环,是比较次数
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int num = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = num;
}
//重点1:比较上次移动和这次的字符串是否一样
if (str.equals(Arrays.toString(arr))) {
break;
}
str=Arrays.toString(arr);
System.out.println("第"+(count++)+"次排序:"+str);
}
System.out.println("内层排序结束---");
}
输出;
原始数据: [1, 2, 3, 5, 4]
开始排序------
第0次排序:[1, 2, 3, 5, 4]
内层排序结束---
结论:
这时还没有有序,内层排序无法减少优化!
原文地址:http://www.cnblogs.com/wmd-l/p/16924692.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性