教程集 > Golang编程 > golang教程 > 正文 Golang基础算法总结

Golang基础算法总结

发布时间：2022-02-01 编辑：jiaochengji.com

教程集为您提供Golang基础算法总结等资源，欢迎您收藏本站，我们将为您提供最新的Golang基础算法总结资源

<h3>Golang基础算法总结</h3> <ul><li>基础算法的思想总结</li><li><ul><li>1.冒泡排序算法</li><li>2.选择排序算法</li><li>3.插入排序算法</li><li>4.快速排序算法</li><li>5.归并排序算法</li></ul></li></ul>

<h1>基础算法的思想总结</h1>

最近在复习算法的时候发现之前的一些基础的算法都忘记了。就在这里总结一下和大家分享，并附上golang的代码实现。

<h2>1.冒泡排序算法</h2>

名字的由来：这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

方法的原理：冒泡排序算法清楚地演示了排序是如何工作的，同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误，则交换它们。重复遍历列表未排序部分的元素，直到完成列表排序。
简单点来讲冒泡排序算法主要思想就是每一次确定一个值。如果是从左开始比较就是通过两两比较找到最大值。如果是从右开始比较就是两两比较找到最小值。如下图所示
时间复杂度：因为冒泡排序重复地通过列表的未排序部分，所以它具有最坏的情况复杂度O(n^2)。

上图描述的就是从左开始比较两两比较确定最大值的例子。

<pre><code class="lang-go hljs">//用golang实现冒泡排序 package main import "fmt" func main() { values := []int{5,6,3,1,8,7,2,4} fmt.Println(values) BubbleAsort(values) BubbleZsort(values) } func BubbleAsort(values []int) { for i := 0; i < len(values)-1; i { for j := i 1; j < len(values); j { if values[i]>values[j]{ values[i],values[j] = values[j],values[i] } } } fmt.Println(values) } func BubbleZsort(values []int) { for i := 0; i < len(values)-1; i { for j := i 1; j < len(values); j { if values[i]<values[j]{ values[i],values[j] = values[j],values[i] } } } fmt.Println(values) } </code></pre> <h2>2.选择排序算法</h2>

算法思想：线性搜索数列并找到最小值。将最小值替换为数列中最左端的数字并进行排序。如果最小值已经在最左端则不进行操作。重复此操作直到数列排序完成。
简单来说就是每次找到数列的最小值并和最左端还没确定的值进行替换。也可以找最大值和最右端没确定的值替换。如下图所示
时间复杂度：最坏时间复杂度：O(n^2)。

上图描述的就是按照找最小值来确定位置的例子。

<pre><code class="lang-go hljs">//golang 实现选择排序算法 package main import "fmt" func main() { numbers := []int{6, 2, 7, 5, 8, 9} SelectSort(numbers) fmt.Println(numbers) } func SelectSort(values []int) { length := len(values) if length <= 1 { return } for i := 0; i < length; i { min := i // 初始的最小值位置从0开始，依次向右 // 从i右侧的所有元素中找出当前最小值所在的下标 for j := length - 1; j > i; j-- { if values[j] < values[min] { min = j } } //fmt.Printf("i:%d min:%d\n", i, min) // 把每次找出来的最小值与之前的最小值做交换 values[i], values[min] = values[min], values[i] //fmt.Println(values) } } </code></pre> <h2>3.插入排序算法</h2>

算法思想：左端的数字已经完成排序。取出那些尚未操作的最左端的数字将这个数字与已经完成排序的数字进行比较如果左边的数字较大则交换两个数字的位置。重复此操作直到出现一个比当前较小的数字或者数字已经到达最左端。如下图所示
时间复杂度：最坏情况下时间复杂度为O(n^2)。最好情况下为O(n)

上图描述的就是插入排序算法的例子。