美文网首页码农笔记
算法和数据结构-冒泡排序

算法和数据结构-冒泡排序

作者: zhaoyunxing | 来源:发表于2020-04-22 20:45 被阅读0次

代码: https://github.com/zhaoyunxing92/algorithms

概念

重复地走访要排序的元素,依次比较两个相邻元素的大小依次完成排序。如图

bubble sort

先看总结

  • 最好时间复杂度:O(n) 也就是数组提前有序
  • 最坏时间复杂度:O(n2)
  • 是一种稳定排序(能保证相对位置不改变)
  • 原地算法(没有依赖额外的资源,仅依赖输出覆盖输入),也就是空间复杂度低

开始推断

开始你想直接暴力点两个for就完事是代码如下

func ViolenceBubbleSort(array []int) time.Duration {
    start := time.Now()
    for i := 0; i < len(array)-1; i++ {
        for j := 0; j < len(array)-1; j++ {
            //如果前面数小于后面数就交换
            if array[j] > array[j+1] {
                // set sort/sort.go:273
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
    ent := time.Now().Sub(start)
    return ent
}

但是聪明的你立马想到了我每次遍历一遍后就已经确定了最大的值了是不是下次比较的时候就可以排除掉它,于是有了下面的代码。动态的长度

func BubbleSort(array []int) time.Duration {
    start := time.Now()
    for end := len(array)-1; end > 0; end-- {
        for begin := 1; begin <= end; begin++ {
            if array[begin] < array[begin-1] {
                array[begin], array[begin-1] = array[begin-1], array[begin]
            }
        }
    }
    ent := time.Now().Sub(start)
    return ent
}

写完代码后你在感叹自己的聪明时又感觉那里怪怪的,你在想如果给的数组本来就有序的那么是不是就不用继续了,激动的你立马想到了添加一个flag记录下是否有序,于是有了下面的代码

func BubbleSort2(array []int) time.Duration {
    start := time.Now()
    for end := len(array)-1; end > 0; end-- {
        sorted:=true
        for begin := 1; begin <= end; begin++ {
            //能进来说明需要排序了
            if array[begin] < array[begin-1] {
                array[begin], array[begin-1] = array[begin-1], array[begin]
                sorted=false
            }
        }
        if sorted {
            break
        }
    }
    return time.Now().Sub(start)
}

就在你暗暗窃喜的时候发现数组排好序的概率太低了,然是如果是部分有序的概率还是有的于是你又修改了代码.记录下最后一次交换的位置

func BubbleSort3(array []int) time.Duration {
    start := time.Now()
    for end := len(array)-1; end > 0; end-- {
        index := 1
        for begin := 1; begin <= end; begin++ {
            if array[begin] < array[begin-1] {
                array[begin], array[begin-1] = array[begin-1], array[begin]
                index = begin
            }
        }
        end = index
    }
    return time.Now().Sub(start)
}

最后

基本使用应该是没有问题了,如果你想了解更多的文章可以微信搜索zhaoyx92,或者扫码关注

zhaoyx92

相关文章

  • 基础排序算法

    一 冒泡排序(buddle sort) 众所周知,冒泡排序一般是我们接触数据结构与算法里面的第一种排序算法。其经典...

  • Python 算法大全

    这个库涵盖了多种算法和数据结构的介绍,比如: 排序算法(冒泡排序、希尔排序、插入排序、桶排序、合并排序、快速排序、...

  • 算法-冒泡排序

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

  • 经典排序算法总结

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

  • C语言:关于数据的几种排序算法

    数据结构的排序算法有很多种。其中,快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法;基数排序、冒泡排序、...

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

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

  • 算法与数据结构路线图

    学习算法与数据结构,深刻理解计算机科学 排序算法:插入、冒泡、选择、希尔、快速、归并、堆排序、计数排序、桶排序、基...

  • 成为顶尖程序员不得不经历的面试题

    一、数据结构与算法基础 · 说一下几种常见的排序算法和分别的复杂度。 · 用Java写一个冒泡排序算法 · 描述一...

  • 面试Java开发常用题的答案

    一、数据结构与算法基础 · 说一下几种常见的排序算法和分别的复杂度。 · 用Java写一个冒泡排序算法 · 描述一...

  • 美团149道面试题,全会拿40Koffer没问题(Java程序员

    一、数据结构与算法基础 · 说一下几种常见的排序算法和分别的复杂度。 · 用Java写一个冒泡排序算法 · 描述一...

网友评论

    本文标题:算法和数据结构-冒泡排序

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