鱼C论坛

 找回密码
 立即注册
查看: 2210|回复: 0

[学习笔记] 冒泡排序算法及其优化

[复制链接]
发表于 2018-10-12 21:28:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 影-死神 于 2018-10-12 22:39 编辑

一. 冒泡排序算法基本思路
        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);

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 07:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表