- 冒泡排序
- 冒泡排序无疑是最为出名的排序算法之一, 总共有八大排序!
- 冒泡的代码还是相当简单的，两层循环，外层冒泡轮数，里层依次比较，江湖中人人尽皆知。
- 我们看到嵌套循环，应该立马就可以得出这个算法的时间复杂度为0(n2)。
- 思考:如何优化?
案例：冒泡排序
public class Name013 {
public static void main(String[] args) {
int[] a = {1, 2, 9, 56,4, 85, 4};
sort(a);
int[] b = sort(a);//调用完我们自己写的排序方法以后，返回一个排序后的数组
System.out.println(Arrays.toString(b));//打印数组
//冒泡排序
//1.比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置
//2.每一次比较，都会产生出一个最大，或者最小的数字;
//3.下一轮则可以少一次排序!
//4.依次循环，直到结束!
}
//方法：srot 需要一个参数(参数：数组array) 首先 把这个数组进行循环
public static int[] sort(int[] array) {
//临时变量 交换位置时存放变量
int temp = 0;
//外层循环，判断我们这个要走多少次;
for (int i = 0; i < array.length - 1; i++) { //i < array.length-1 是为了不让它溢出
// System.out.print(array.length-1);//数组-1的长度 如：int[] a = {1, 2, 9, 56,4, 85, 4}; 数组-1长度为：6 是为了不让它溢出 而数组原本长度为 7
// System.out.println(" 为数组-1的长度t"+"数组原本长度是 "+array.length);//数组原本长度
// System.out.println("====================");
//内层循环，比价判断两个数，如果第一个数，比第二个数大，则交换位置 刚开始array:{1, 2, 9, 56,4, 85, 4}
for (int j = 0; j < array.length - 1 - i; j++) {//如果 第一次 i=0 j=0 < 数组长度-1-i=6 执行以下语句完 array:{2,1,9,56...} 第二次i=0 因j++ j=1 < 数组长度-1-i=6 执行以下语句完 array:{2,9,1,56...} 以此类推
if (array[j + 1] > array[j]) { //对比大小交换位置 由大到小排序 判断第一次：j=0 当array[j=0 + 1]=2 > array[j=0]=1 执行以下语句 判断第二次：j=1 当array[j=1 + 1]=9 > array[j=1]=1 根据已执行完一次的数组位置来的 执行以下语句
// if (array[j + 1] < array[j]) { //由小到大排序
temp = array[j];//第一次j=0：array[j=0]=1 赋给 temp 此时：temp=1 第二次j=1：根据已执行完一次的数组位置来的array:{2,1,9,56...} array[j=1]=1 赋给 temp=1 此时：temp=1
array[j] = array[j + 1];//第一次j=0: array[j=0 + 1]=2 赋给 array[j=0]=1 此时：array[j=0]=2 第二次j=1：根据已执行完一次的数组位置来的array:{2,1,9,56...} array[j=1 + 1]=9 赋给 array[j=1]=1 此时：array[j=1]=9
array[j + 1] = temp;//第一次j=0：temp=1 赋给 array[j=0 + 1]=2 此时：array[j=0 + 1]=1 第二次j=1：temp=1 赋给 array[j=1 + 1]=9 此时：array[j=1 + 1]=1
}
}
}
// if (flag == false) {
// break;
// }
return array;//返回值
}
}
案例：优化冒泡排序如果时已经拍好序的就不许要再排减少资料浪费
public class Name013 {
public static void main(String[] args) {
// int[] a = {1, 2, 3, 4,4, 5, 6};
int[] a = {1, 2, 9, 56,4, 85, 4};
sort(a);
int[] b = sort(a);//调用完我们自己写的排序方法以后，返回一个排序后的数组
System.out.println(Arrays.toString(b));//打印数组
//冒泡排序
//1.比较数组中，两个相邻的元素，如果第一个数比第二 个数大，我们就交换他们的位置
//2.每-一次比较，都会产生出一一个最大， 或者最小的数字;
//3.下一 轮则可以少一次排序!
//4.依次衙环，直到结束!
}
//方法：srot 需要一个参数(参数：数组array) 首先 把这个数组进行循环
public static int[] sort(int[] array) {
//临时变量 交换位置时存放变量
int temp = 0;
//外层循环，判断我们这个要走多少次;
for (int i = 0; i < array.length - 1; i++) { //i < array.length-1 是为了不让它溢出
// System.out.print(array.length-1);//数组-1的长度 如：int[] a = {1, 2, 9, 56,4, 85, 4}; 数组-1长度为：6 是为了不让它溢出 而数组原本长度为 7
// System.out.println(" 为数组-1的长度t"+"数组原本长度是 "+array.length);//数组原本长度
// System.out.println("====================");
boolean flag = false; //通过flag标识位减少没有意义的相同比较
//内层循环，比价判断两个数，如果第一个数，比第二个数大，则交换位置 刚开始array:{1, 2, 9, 56,4, 85, 4}
for (int j = 0; j < array.length - 1 - i; j++) {//如果 第一次 i=0 j=0 < 数组长度-1-i=6 执行以下语句完 array:{2,1,9,56...} 第二次i=0 因j++ j=1 < 数组长度-1-i=6 执行以下语句完 array:{2,9,1,56...} 以此类推
// if (array[j + 1] > array[j]) { //对比大小交换位置 由大到小排序 判断第一次：j=0 当array[j=0 + 1]=2 > array[j=0]=1 执行以下语句 判断第二次：j=1 当array[j=1 + 1]=9 > array[j=1]=1 根据已执行完一次的数组位置来的 执行以下语句
if (array[j + 1] < array[j]) { //由小到大排序
temp = array[j];//第一次j=0：array[j=0]=1 赋给 temp 此时：temp=1 第二次j=1：根据已执行完一次的数组位置来的array:{2,1,9,56...} array[j=1]=1 赋给 temp=1 此时：temp=1
array[j] = array[j + 1];//第一次j=0: array[j=0 + 1]=2 赋给 array[j=0]=1 此时：array[j=0]=2 第二次j=1：根据已执行完一次的数组位置来的array:{2,1,9,56...} array[j=1 + 1]=9 赋给 array[j=1]=1 此时：array[j=1]=9
array[j + 1] = temp;//第一次j=0：temp=1 赋给 array[j=0 + 1]=2 此时：array[j=0 + 1]=1 第二次j=1：temp=1 赋给 array[j=1 + 1]=9 此时：array[j=1 + 1]=1
flag = true;//每循环一次只要让里面flag为true 就是排过序 如果这个里面没有产生比较的情况下 flag就不会被至于true 为false
}
}
if (flag == false) {//如果flag 等于 false 那就是没有做里面的判断、没有进行比较 就说明结束 退出了
break;//退出
}
}
return array;//返回值
}
}
