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

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

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

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

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


冒泡排序

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

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

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

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

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

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

代码如下:

funcbubbleSort(data []int){fori :=0; i <len(data); i++ {forj :=0; j <len(data)-i-1; j++ {ifdata[j] > data[j+1] {data[j], data[j+1] = data[j+1], data[j]}}}}

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

funcbubbleSort(data []int){swap :=truefori :=0; i <len(data) && swap; i++ {swap =falseforj :=0; j <len(data)-i-1; j++ {ifdata[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:

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

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

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

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

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

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

代码实现:

funcselectionSort(data []int){fori :=0; i <len(data)-1; i++ {min := iforj := i +1; j <len(data); j++ {ifdata[j] < data[min] {min = j}}data[i], data[min] = data[min], data[i]}}

选择排序相关复杂度:

时间复杂度
最坏O(n2)
最好O(n2)
平均O(n2)
空间复杂度O(1)
是否稳定

插入排序

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

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

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

代码实现如下:

funcinsertionSort(data []int){fori :=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 的排序相关题目会在排序专题结束之后进行推荐。


往期文章推荐:

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

rosedb 连续两天上榜

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

我学 Go 语言这一年


题图:from wallheaven.cc

原创文章 Go语言算法之美—基础排序,版权所有
如若转载,请注明出处:https://www.itxiaozhan.cn/20229535.html

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注