专栏首页roseduan写字的地方Go 语言算法之美—基础排序

Go 语言算法之美—基础排序

前言:录制 rosedb 视频的时候,挖了个坑,说要用 Go 语言实现常见的数据结构和算法,虽然现在这样的文章已经很多了,但是玫瑰哥?有坑必填!只能硬着头皮写了,这个系列,就叫做 Go 语言算法之美吧!

排序是一个十分古老的问题,也是计算机领域很经典的算法问题之一,后续的几篇文章,我将对常见的排序算法进行讲述。

我将会附上完整的代码,并且推荐一些相关的 Leetcode 题目,不仅可以用来学习巩固算法知识,还能够帮助你在面试当中,更加的游刃有余。

本篇文章介绍三种基础排序算法:冒泡排序、选择排序、插入排序。


冒泡排序

冒泡排序基于比较并交换,基本思路是遍历数据,如果相邻的元素大小不等,则交换它们的位置,如此循环往复,直到数据完全有序。

如下图,有测试数据 -2 45 0 11 -9。

在第一次遍历当中,会将数据中最大值 45 移动至末尾,然后在除了 45 的数据内再次遍历,将最大值移动至 45 之前。这样遍历完最后一个元素,数据即是有序的了。

下图比较直观的展示了冒泡排序的流程:

代码如下:

func bubbleSort(data []int) {
   for i := 0; i < len(data); i++ {
      for j := 0; j < len(data)-i-1; j++ {
         if data[j] > data[j+1] {
            data[j], data[j+1] = data[j+1], data[j]
         }
      }
   }
}

这里有一个小的优化点,如果数据本来就是有序的,例如 1 3 4 5 6 ,遍历一次之后,会发现没有任何数据进行交换,可以提前退出,不用继续进行遍历了,代码上可以进行优化,如下:

func bubbleSort(data []int) {
   swap := true
   for i := 0; i < len(data) && swap; i++ {
      swap = false
      for j := 0; j < len(data)-i-1; j++ {
         if data[j] > data[j+1] {
            data[j], data[j+1] = data[j+1], data[j]
            swap = true
         }
      }
   }
}

冒泡排序相关复杂度:

时间复杂度

最坏

O(n2)

最好

O(n)

平均

O(n2)

空间复杂度

O(1)

是否稳定

选择排序

选择排序也很容易理解,对于一个无序的数组,我们每次都从数组中寻找最小值,并把它和第一个元素交换。

如下图,有测试数据 20 12 10 15 2,第一次遍历,寻找到最小值是 2:

并将其与数组的第一个元素进行交换:

然后在剩下的数据中继续寻找最小值,然后将其与数组第二个元素交换,如此循环往复,直到最后一个数据,这样整个数组便是有序的了。

下面这张动图可以帮助你理解选择排序的整个过程:

代码实现:

func selectionSort(data []int) {
   for i := 0; i < len(data)-1; i++ {
      min := i
      for j := i + 1; j < len(data); j++ {
         if data[j] < data[min] {
            min = j
         }
      }
      data[i], data[min] = data[min], data[i]
   }
}

选择排序相关复杂度:

时间复杂度

最坏

O(n2)

最好

O(n2)

平均

O(n2)

空间复杂度

O(1)

是否稳定

插入排序

回想一下我们在玩纸牌游戏时,是如何将手中的纸牌变得有顺序的?当新来了一张纸牌,我们会在手中已有的纸牌中查找到合适的位置,将其插入。

插入排序也是这样的,依次遍历数组中的每一个数据,将其插入到合适的位置,下面的这张动图比较形象的说明了这个过程:

代码实现如下:

func insertionSort(data []int) {
   for i := 0; i < len(data)-1; i++ {
      j, k := i+1, data[i+1]
      for ; j > 0 && data[j-1] > k; j-- {
         data[j] = data[j-1]
      }
      data[j] = k
   }
}

插入排序相关复杂度:

时间复杂度

最坏

O(n2)

最好

O(n)

平均

O(n2)

空间复杂度

O(1)

是否稳定

备注:完整代码我放到了我的 Github 上面,地址:

https://github.com/roseduan/Go-Algorithm

Leetcode 的排序相关题目会在排序专题结束之后进行推荐。


本文分享自微信公众号 - roseduan写字的地方(rose_duan),作者:roseduan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Go 语言算法之美—进阶排序

    上一篇文章讲述了几种基础的排序算法,可以回顾一下:Go 语言算法之美—基础排序,这几种算法平均情况下的时间复杂度都是 O(n2),在大规模数据下是非常低效的,所...

    roseduan
  • Go 语言算法之美—线性排序

    前面的两篇文章分别讲述了基础的排序算法,以及应用更加广泛的 O(nlogn) 的排序算法,今天再来看看几种特殊的线性排序算法,之所以叫线性,是因为他们的主要思想...

    roseduan
  • 【从零开始学习Go语言】十.基础算法之冒泡排序

    举个例子说明一下,比如有一个数组:[3 2 1 0],需要将该数组进行升序排序,即排序成:[0 1 2 3]。

    一只特立独行的兔先生
  • Go 语言基础--语法基础

    同其他语言一样go也有 算术运算符、关系运算符、逻辑运算符、位运算符、赋值运算符 这几类,作用也是一致的,这里就不过多赘述了。 算数运算符:+、-、*、/、%...

    邹志全
  • 基础算法之排序算法

    快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

    王脸小
  • go语言学习之基础语法

    友情提示,以下fmt.Printf语句是打印结果,类似于java的System.out.println;

    简单的程序员
  • C语言基础排序方法

    C语言最基础的排序方法,在课本上共有三种,第一种起泡法,第二种选择法,第三种插入法。

    布衣者
  • go语言十大排序算法总结

    选择排序 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的...

    李海彬
  • Go语言归并排序算法实现

    算法导论的伪代码: MERGE 函数是合并两个已经排好序的序列。 下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组...

    李海彬
  • go语言十大排序算法总结

    选择排序 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的...

    李海彬
  • Go语言归并排序算法实现

    算法导论的伪代码: MERGE 函数是合并两个已经排好序的序列。 下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组...

    李海彬
  • 【C语言】排序算法之冒泡排序

    冒泡排序(Bubble Sort):是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复...

    Regan Yue
  • 【C语言】排序算法之选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

    Regan Yue
  • Go(二) 语言基础语法

    Go 程序可以由多个标记组成,可以是关键字,标识符,常量,字符串,符号。如以下 GO 语句由 6 个标记组成:

    一觉睡到小时候
  • 算法学习之排序基础

    #include <iostream> #include <algorithm> using namespace std; void selectionSo...

    慕白
  • 基础算法系列之排序算法-2.冒泡排序

    上篇文章给大家讲述了二分查找算法,现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法,可以将一个无序的序列排成有序。它将会是我们以后...

    ACM算法日常
  • Go之排序算法sort

    Go的pkg提供了一个排序的包sort,用于对slices和用户自定义的类型进行排序操作。原文参考:

    灰子学技术
  • 基础排序算法

    假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么选择排序的排序流程为:

    Java学习录
  • 基础排序算法

    使用比较运算符” < ”和” > ”,将相容的序放到输入中,且除了赋值运算符外,这两种运算是仅有的允许对输入数据进行的操作,在这些条件下...

    我是一条小青蛇

扫码关注云+社区

领取腾讯云代金券