美文网首页
算法-冒泡排序

算法-冒泡排序

作者: 王多鱼2 | 来源:发表于2019-10-25 23:53 被阅读0次

冒泡排序(Bubble Sort)

1,正常写法

① 从头开始比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置
执行完一轮后,最末尾那个元素就是最大的元素
② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①,直到全部元素有序

 Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length-1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                }
            }
        }

  System.out.println(" count = " + count);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "_");
        }

 count = 28
3_4_5_5_6_7_7_8_

2,优化1

如果序列已经完全有序,可以提前终止冒泡排序

  Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length -1; end > 0; end--) {
            boolean sorted = true ;
            for (int begin = 1; begin <=end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sorted = false ;
                }
            }

            if(sorted) break;
        }

2,优化2

如果序列尾部已经局部有序,可以记录最后1次交换的位置,减少比较次数

     Integer[] array = {7, 3, 5, 8, 6, 7, 4, 5};
        int count = 0 ;
        for (int end = array.length -1; end > 0; end--) {
            int  sortedIndex = 1 ;
            for (int begin = 1; begin <=end; begin++) {
                count ++ ;
                if (array[begin] < array[begin - 1]) {
                    int temp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = temp;
                    sortedIndex = begin ;
                }
            }

           end = sortedIndex;
        }

3,优化方式:鸡尾酒排序,也叫双向冒泡排序,看到别人的 ,优不优,我没研究

public static Integer[] sort(Integer[] arr){
    //依次将最大的数放置到数组末尾,将第二大的数放到倒数第二位...
    boolean changed;
    for(int i = 0;i < arr.length/2;i++){
        changed = false;
        //从前往后,比较相邻两个数,把大的放在后边.之前已放置成功的可以不再参与比较
        for(int j = i;j < arr.length-1-i;j++){

            if(arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
                changed =true;
            }
        }
        if(!changed){
            break;
        }
        for(int j = arr.length-1-i; j > i; j--){

            if(arr[j]<arr[j-1]) {
                swap(arr,j,j-1);
                changed = true;
            }
        }
        if(!changed){
            break;
        }
    }
    return arr;
}

public static void swap(Integer[] arr, int pos1, int pos2){
    int temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

◼ 最坏、平均时间复杂度:O(n2)
◼ 最好时间复杂度:O(n)
◼ 空间复杂度:O(1)

相关文章

  • 算法-冒泡排序

    算 法:冒泡排序算法时间复杂度: 冒泡排序算法概述 冒泡排序伪代码 冒泡排序实现 冒泡排序算法概述 冒泡排...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 七大排序算法之冒泡排序

    七大排序算法之冒泡排序 @(算法笔记)[排序算法, 冒泡排序, C++实现] 冒泡排序介绍 冒泡排序是七大排序算法...

  • 前端算法学习-第一篇

    冒泡排序算法 冒泡排序算法是最慢的排序算法之一,也是最容易实现的排序算法。之所以叫冒泡排序是因为使用这种算法排序时...

  • iOS算法总结-冒泡排序

    iOS算法总结-冒泡排序 iOS算法总结-冒泡排序

  • python 冒泡排序和选择排序算法

    插入排序算法 冒泡排序算法

  • Java基础(冒泡排序与选择排序)

    冒泡排序 冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡排序算法在刚开始研究排序技术时是一...

  • 基本算法——快速排序算法

    快速排序算法是对冒泡算法的改进。所以我们首先来简单的谈谈冒泡算法。 1.冒泡算法 冒泡排序(Bubble S...

  • 7.4-全栈Java笔记:三种经典算法

    冒泡排序算法 冒泡排序是最常用的排序算法,在笔试中也非常常见,能手写出冒泡排序算法可以说是基本的素养。 算法重复地...

  • 算法:冒泡排序

    本文内容:1、什么是冒泡排序?2、冒泡排序的 C/OC 实现与算法分析。 算法总目录:算法? 1、什么是冒泡排序?...

网友评论

      本文标题:算法-冒泡排序

      本文链接:https://www.haomeiwen.com/subject/lgzevctx.html