本文转载自微信公众号《roseduan写的地方》,作者roseduan转载本文请联系roseduan写的地方公众号。录制rosedb视频的时候,挖了一个坑,说要用Go语言实现常用的数据结构和算法。虽然现在已经有很多这样的文章了,玫瑰哥??,这个系列堪称Go语言算法之美!排序是一个非常古老的问题,也是计算机领域的经典算法问题之一。在接下来的几篇文章中,我将介绍常见的排序算法。我会附上完整的代码,并推荐一些相关的Leetcode题目,不仅可以用来学习和巩固算法知识,也可以帮助你在面试中游刃有余。本文介绍了三种基本的排序算法:冒泡排序、选择排序和插入排序。冒泡排序冒泡排序基于比较和交换。基本思想是遍历数据。如果相邻元素大小不同,则交换它们的位置,依此类推,直到数据完全有序。如下图,有测试数据-245011-9。第一次遍历时会将数据中的最大值45移动到末尾,然后在除45以外的数据中再次遍历,将最大值移动到45之前。这样遍历完最后一个元素后,数据是有序的。下图更直观的展示了冒泡排序的过程:代码如下:funcbubbleSort(data[]int){fori:=0;idata[j+1]{data[j],data[j+1]=data[j+1],data[j]}}}}这是一个小优化点,如果数据原本是有序的,比如13456,遍历一次后,会发现没有数据交换,可以提前退出,不需要继续遍历,代码可以进行优化,如下:funcbubbleSort(data[]int){swap:=truefori:=0;idata[j+1]{data[j],data[j+1]=data[j+1],data[j]swap=true}}}}冒泡排序相关的复杂度:时间复杂度最差O(n2)最好O(n)平均O(n2)空间复杂度O(1)是否稳定?选择排序选择排序也很容易理解。对于无序数组,我们每次都从数组中寻找最小值。并将其与第一个元素交换。如下图,有测试数据201210152,第一次遍历,找到最小值为2:并与数组第一个元素交换:然后继续在剩余数据中寻找最小值,然后和数组的第二个元素交换,以此类推,直到最后一个数据,这样整个数组就有序了。下面的动画可以帮助大家理解选择排序的全过程:代码实现:funcselectionSort(data[]int){fori:=0;i0&&data[j-1]>k;j--{data[j]=data[j-1]}data[j]=k}}插入排序相关复杂度:时间复杂度最差O(n2)bestO(n)averageO(n2)spacecomplexityO(1)稳定与否是注:我把完整的代码放在了我的Github上,地址:https://github.com/roseduan/围棋算法