IT干货网

冒泡排序

luoye 2022年03月12日 编程设计 189 0

冒泡排序

以下代码实现冒泡排序:

package com.cxf.array; 
 
import java.lang.reflect.Array; 
import java.util.Arrays; 
 
public class Demo1 { 
    public static void main(String[] args) { 
        int[] array1 = {5,7,9,2,3,4,1}; 
        System.out.println(Arrays.toString(array1)); 
        System.out.println(Arrays.toString(bubble_sort(array1))); 
    } 
    public static int[] bubble_sort(int[] array){ 
        int temp; 
        for (int i = 0; i < array.length-1; i++) { 
            for (int j = 0; j < array.length-i-1; j++) { 
                if(array[j]>array[j+1]){ 
                    temp = array[j]; 
                    array[j] = array[j+1]; 
                    array[j+1] = temp; 
                } 
            } 
        } 
        return array; 
    } 
} 
 

输出结果:

[5, 7, 9, 2, 3, 4, 1] 
[1, 2, 3, 4, 5, 7, 9] 

冒泡排序中使用两层循环。

外层循环每次至少得到一个最值,例如3个数字{3,2,1},第一次循环得到最大值3,排序结果{2,1,3},第二次循环得到除了3以外的最大值2,排序结果{1,2,3},之后无需再排序。因此对于长度为n的数组,外层循环次数应为n-1。

内层循环每次比较一次大小,总的比较次数和已经进行了外层循环的次数有关。起初需要多次比较,后期需要比较的次数减少。

对冒泡排序进行改进

package com.cxf.array; 
 
import java.lang.reflect.Array; 
import java.util.Arrays; 
 
public class Demo1 { 
    public static void main(String[] args) { 
        int[] array1 = {5,7,9,2,3,4,1}; 
        System.out.println(Arrays.toString(array1)); 
        System.out.println(Arrays.toString(bubble_sort(array1))); 
    } 
    public static int[] bubble_sort(int[] array){ 
        int temp; 
        for (int i = 0; i < array.length-1; i++) { 
            boolean flag = true; 
            for (int j = 0; j < array.length-i-1; j++) { 
                if(array[j]>array[j+1]){ 
                    temp = array[j]; 
                    array[j] = array[j+1]; 
                    array[j+1] = temp; 
                    flag =false; 
                } 
            } 
            if(flag)break; 
        } 
        return array; 
    } 
} 
 

输出结果:

 [5, 7, 9, 2, 3, 4, 1] 
 [1, 2, 3, 4, 5, 7, 9] 

此次改进在第15行增加了flag标志,初始值为true,若一次外层循环中,有元素交换的现象,则flag变为false。反之未发生元素交换,表明整个数组已经排序完成,flag仍为true,直接break退出排序,避免了后面无用的排序过程。


评论关闭
IT干货网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!