冒泡排序算法及其优化

影-死神

一. 冒泡排序算法基本思路
        1. 从第一位开始，每次比较相邻元素，根据大小来交换元素的位置，序号增加一后循环执行此步骤
        2. 一轮循环完后，无序区中最大的元素被交换到末尾，作为有序区，最大元素之前作为无序区
        3. 将无序区按照上述步骤循环执行，直到无序区的元素个数为1
        算法的时间复杂度：
                由于需要执行两个for循环，所以时间复杂度为 n**2
        Java代码实现:

public class BubbleSort {
    private static void sort1(int[] list) {
        int temp;
        for (int i=0;i<list.length;i++) {
            for (int j=0;j<list.length-i-1;j++) {
                if (list[j] > list[j+1]) {
                    temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;
                }
            }
        }
    }  
    public static void main(String[] args) {
        int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
        
        sort1(list);
        
        for (int i=0;i<list.length;i++) {
            System.out.print(list[i] + " ");
        }
    }
}

二. 优化冒泡算法
        发现问题1：如果数列经过几轮排序后，已经是有序的了，此时，循环仍然继续执行
        优化思路1：每轮循环执行后，判断数列是否有序，如果有序，直接结束循环
        实现方法1：
                1. 设置一个标记，每轮执行前标记为有序
                2. 如果执行过程中有元素交换，说明数列不是有序的，标记为无序
                3. 执行完成后，如果标记为仍为有序，则跳出循环
       Java代码实现：

public class BubbleSort {
    private static void sort2(int[] list) {
            int temp;
            for (int i=0;i<list.length;i++) {
                    boolean isSorted = true;
                    for (int j=0;j<list.length-i-1;j++) {
                            if (list[j] > list[j+1]) {
                                    temp = list[j];
                                    list[j] = list[j+1];
                                    list[j+1] = temp;
                                    isSorted = false;
                            }
                    }
                   
                    if (isSorted) {
                            break;
                    }
            }
    }
   
    public static void main(String[] args) {
            int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
           
            sort2(list);
           
            for (int i=0;i<list.length;i++) {
                    System.out.print(list + " ");
            }
    }
}

        
        发现问题2：在执行某轮排序前，无序区中，最后几位已经是无序区中最大值的有序排列
        优化思路2：若某轮执行后，发现上述情况，直接将最大值的有序排列并入有序区
        优化方法2：
                1. 在每轮排序的最后记录最后一次元素交换的位置，将此位置作为边界，之后的为有序区
                2. 将每轮排序的判断条件改为：从0到边界
        Java代码实现：

public class BubbleSort {
        private static void sort3(int[] list) {
                int temp;
                //最后交换元素的位置
                int index = 0;
                //无序和有序的边界
                int sortBorder = list.length -1;
                for (int i=0;i<list.length;i++) {
                        boolean isSorted = true;
                        for (int j=0;j<sortBorder;j++) {
                                if (list[j] > list[j+1]) {
                                        temp = list[j];
                                        list[j] = list[j+1];
                                        list[j+1] = temp;
                                       
                                        isSorted = false;
                                        //不要在for循环内改变for循环判断的条件，即不能直接使用sortBorder = j
                                        index = j;
                                }
                        }
                        sortBorder = index;
                       
                        if (isSorted) {
                                break;
                        }
                }
        }
       
        public static void main(String[] args) {
                int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
               
                sort3(list);
               
                for (int i=0;i<list.length;i++) {
                        System.out.print(list + " ");
                }
        }
}  

   

三. 所有代码

public class BubbleSort {
        private static void sort1(int[] list) {
                int temp;
                for (int i=0;i<list.length;i++) {
                        for (int j=0;j<list.length-i-1;j++) {
                                if (list[j] > list[j+1]) {
                                        temp = list[j];
                                        list[j] = list[j+1];
                                        list[j+1] = temp;
                                }
                        }
                }
        }
       
        private static void sort2(int[] list) {
                int temp;
                for (int i=0;i<list.length;i++) {
                        boolean isSorted = true;
                        for (int j=0;j<list.length-i-1;j++) {
                                if (list[j] > list[j+1]) {
                                        temp = list[j];
                                        list[j] = list[j+1];
                                        list[j+1] = temp;
                                        isSorted = false;
                                }
                        }
                       
                        if (isSorted) {
                                break;
                        }
                }
        }
       
        private static void sort3(int[] list) {
                int temp;
                //最后交换元素的位置
                int index = 0;
                //无序和有序的边界
                int sortBorder = list.length -1;
                for (int i=0;i<list.length;i++) {
                        boolean isSorted = true;
                        for (int j=0;j<sortBorder;j++) {
                                if (list[j] > list[j+1]) {
                                        temp = list[j];
                                        list[j] = list[j+1];
                                        list[j+1] = temp;
                                       
                                        isSorted = false;
                                        //不要在for循环内改变for循环判断的条件，即不能直接使用sortBorder = j
                                        index = j;
                                }
                        }
                        sortBorder = index;
                       
                        if (isSorted) {
                                break;
                        }
                }
        }
       
        public static void main(String[] args) {
                int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
               
                //sort1(list);
                //sort2(list);
                sort3(list);
               
               
                for (int i=0;i<list.length;i++) {
                        System.out.print(list + " ");
                }
        }
}

另外，排序算法在java中可直接使用java.util.Arrays.sort(list);