Go语言排序算法之插入排序与生成随机数详解

本篇文章给大家分享《Go语言排序算法之插入排序与生成随机数详解》，覆盖了Golang的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

前言

排序，对于每种编程语言都是要面对的。这里跟大家一起分享golang实现一些排序算法，并且说明如何生成随机数。下面话不多说了，来一起看看详细的介绍吧。

经典排序算法

算法的学习非常重要，是检验一个程序员水平的重要标准。学习算法不能死记硬背，需要理解其中的思想，这样才能灵活应用到实际的开发中。

七大经典排序算法

• 插入排序
• 选择排序
• 冒泡排序
• 希尔排序
• 归并排序
• 堆排序
• 快速排序

插入排序

先考虑一个问题：对于长度为n的数组，前n-1位都是递增有序的，如何排序？

     1.从第1位至第n-1位遍历数组，发现第n位数字应该放在第k位

     2.把第k位至第n-1位的数字依次向后挪一位

     3.这样长度为n的数组就是递增有序的了

具体实现方法：

package main
import "fmt" 

func insertionSort(arr []int) {
  for i := 1; i = 0; j-- {
    if value 

<p><strong>复杂度：</strong><br></p>
<p>时间复杂度：O(n*n）<br></p>
<p>空间复杂度：额外空间O(1)</p>
<p>O表达式（Big O notation）通常用来在计算机科学中表示算法的复杂度，包括：<br></p>
<p>时间复杂度：衡量算法的运行时间<br></p>
<p>空间复杂度：衡量算法运行所占的空间，比如内存或硬盘等</p>
<p>一般情况下，O表达式代表的是最坏情况下的复杂度。</p>
<p>算法分析也是如此，在n个随即数中查找某个数字，最好的情况是第一个数字就是，此时时间复杂度为O(1)，若最后一个数字才是我们要找的，那么时间复杂度是O(n)，这是最坏的情况。而平均运行时间是从概率的角度看，若数字在每一个位置都可能出现，则平均查找次数为n/2次。</p>
<p>平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。即，时间复杂度是最坏情况下的时间复杂度。</p>
<p>常见的算法时间复杂度由小到大依次为：</p>

<pre class="brush:plain;">
O(1)<o log2 n><p>这里的O就是一般表示复杂度的一个标志，类似计算复杂度的函数名称一样。</p>
<p>两种复杂度都是一种估算，<br></p>
<p>估算的方式就是根据代码的逻辑，分析出对于复杂度的公式。</p>
<p>在时间复杂度上，主要记录的是带有变量的循环。<br></p>
<p>比如for (i = 0; i 
</p>
<p>而 x = n + 1; y = x + 1; z = x + y;虽然是三条语句，但是没有循环操作，所以理解为O(1)</p>
<p>在空间复杂度上，主要记录的是带有变量的空间申请。<br></p>
<p>比如int[n] x;可以理解为O(n)<br></p>
<p>而 int x; int y; int z;虽然是三个变量，但是没有变化的申请操作，所以理解为O(1)</p>
<p>大O符号是用于描述函数渐近行为的数学符号。既可以表示无穷大渐近也可以表示<br></p>
<p>无穷小渐近。看你是用在算法还是描述数学函数估计中的误差项</p>
<p><strong>再来看看我们的插入排序：</strong></p>
<ul><li>当数组是逆序的时候，时间复杂度是O(n*n）</li>
  <li>当数组几乎是有序的时候，时间复杂度是O(n）</li>
</ul><p>另外插入排序的overhead特别小，可以理解为常数等于1</p>
<p>在实际应用中，常数也是一个很重要的因素。有的算法复杂度低，但是常数较高；再加上数据的特点，有时候反而比不上复杂度更高但是常数低的算法。</p>
<p><strong>在理解插入排序算法的过程中，应该要明白一个算法思想：</strong></p>
<ul><li>把问题分解为子问题</li>
  <li>找到问题的初始状态</li>
  <li>从问题的初始状态，通过子问题，一步步得到最终的解</li>
</ul><p>实际应用中，要灵活的选择算法，有几个重点要考虑的：</p>
<ul><li>复杂度：包括时间复杂度，空间复杂度，常数等</li>
  <li>实现复杂度：算法实现起来很难，不易于测试和维护的话，也是很大的问题</li>
  <li>适用性：在特定的业务场景下，是否有更合适的算法？</li>
</ul><p>总的来说，要具体情况具体分析，在满足业务的同时要简洁的解决问题。</p>
<p><span style="color: #ff0000"><strong>go 生成区间随机数</strong></span></p>

<pre class="brush:js;">
// 函　数：生成随机数 
// 概　要： 
// 参　数： 
//  min: 最小值 
//  max: 最大值 
// 返回值： 
//  int64: 生成的随机数 
func RandInt64(min, max int64) int64 { 
 if min >= max || min == 0 || max == 0 { 
  return max 
 } 
 return rand.Int63n(max-min) + min 
} 

参考文章： 【BAT后台入门】第二课：数组与排序

总结

今天关于《Go语言排序算法之插入排序与生成随机数详解》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于golang的内容请关注golang学习网公众号！