图解数据结构和算法(三) · 冒泡排序(Bubble Sort) java实现

图解数据结构和算法(三) · 冒泡排序(Bubble Sort) java实现

java实现冒泡排序算法

简介

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

时间复杂度 0(n2)

  • 如果数组已经是正序排列的情况,那么只需要循环一次数组即可,这时候的时间复杂度为O(n)

  • 如果数组刚好逆序,那么需要n-1趟对比,每次需要n-i次比较。最终可换算出冒泡排序最坏的时间复杂度为0(n2)

插入过程动图

DubboSort

算法原理

  • 1 比较相邻的2个元素,如果第一个比第二个大,就交换他们的位置

  • 2 因为每一对相邻元素都做同样的事情,所以,最大的元素最终会被移动到最后面

  • 3 针对所有元素都做上面同样的事情,除了最后一个

  • 4 在持续减少的元素中,重复做对比操作,直到无对比对象为止,这时候,排序已经完成

java实现

public class BubbleSort {

    private static Integer[] sortArrays = {256,50,354,64,213,65,323,65,243,54,76,2,765,342,765,453};

    public static void main(String[] args) {

        Integer tmpVal;
        int endIndex = sortArrays.length;

        for (int j = endIndex;j >= 0;j -- ){

            for (int i = 0; i < sortArrays.length; i++) {
                tmpVal = sortArrays[i];

                //判断是否已经达到了上一次循环遍历的最终位置,如果达到,说明在之后的元素都是已经拍好序的,无需往后遍历
                if(i >= (endIndex - 1)){
                    --endIndex;
                    //每循环一次,结束点往前加1。参照上图中的模式,每次循环玩,都会产生出一个最大值在最后边
                    break;
                }
                //比较相邻的2个元素,如果前者大于后者,则互换位置
                if(sortArrays[i] > sortArrays[i + 1]){
                    //如果前一个大于后一个,则交换位置
                    sortArrays[i] = sortArrays[i + 1];
                    sortArrays[i + 1] = tmpVal;
                }
            }
        }
    }
}

总结

冒泡排序的技巧就是在于,每次循环总会在剩余数组中筛选出一个最大节点放在最后的位置(endIndex),这也就意味着endIndex会越来越小,如果endIndex = 0,则说明已经排序完毕

上一章(图解数据结构和算法(二) · 选择排序 (select-sort))

下一章(图解数据结构和算法(四) · 归并排序(merge-sort)

# 算法  java  排序 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×