普通冒泡排序
public class ArrTest {
public static void main(String[] args) {
int[] arr = new int[20];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 100);
}
for(int i = 0;i < arr.length - 1;i++){
for(int j = 0;j < arr.length - i - 1;j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void printArr(int[] arr){
for(int k: arr){
System.out.print(k + " ");
}
System.out.println();
}
}
一次只能查找出一个最大值或者最小值
优化一
添加一个变量,控制外层循环,如果整个循环都没有进行排序的话则直接返回,默认flag是true,内层循环每次遍历如果有位置的改变则flag变为false,最后在内层循环
完成之后查看flag的值是否改变了,如果没有改变则表示整轮循环中没有涉及到位置的改变,可以直径返回,不在进行排序
public class ArrTest {
public static void main(String[] args) {
int[] arr = new int[20];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 100);
}
for(int i = 0;i < arr.length - 1;i++){
boolean flag = true;
for(int j = 0;j < arr.length - i - 1;j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if(flag){
break;
}
}
}
public static void printArr(int[] arr){
for(int k: arr){
System.out.print(k + " ");
}
System.out.println();
}
}
优化二 鸡尾酒排序,双向冒泡
这种排序的方法是每次外层循环之后,在内层循环都会找到一个最大数和最小数,分别放在数组的两端,代码实现
public class ArrTest {
public static void main(String[] args) {
int[] arr = new int[20];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 100);
}
int len = arr.length;
for(int i = 0;i < len;i++){
for(int j = 0;j < len - i -1;j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
printArr(arr);
for(int k = len - i - 1;k > 0;k--){
if(arr[k] < arr[k - 1]){
int temp = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = temp;
}
}
printArr(arr);
}
System.out.println();
}
public static void printArr(int[] arr){
for(int k: arr){
System.out.print(k + " ");
}
System.out.println();
}
}