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]
内层排序结束---
结论:
这时还没有有序,内层排序无法减少优化!
标签:11,10,arr,int,内层,算法,排序 From: https://www.cnblogs.com/wmd-l/p/16924692.html