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

前言

排序，对于每种编程语言都是要面对的。这里跟大家一起分享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 < len(arr); i++ {
   value := arr[i]

   for j := i - 1; j >= 0; j-- {
    if value < arr[j] {
     arr[j+1], arr[j] = arr[j], value
    } else {
     break
    }

   }
  }

}

func main() {
 arr := []int{6, 5, 4, 3, 2, 1, 0}
 insertionSort(arr)

 fmt.Println("Sorted arr: ", arr)
}

复杂度：

时间复杂度：O(n*n）

空间复杂度：额外空间O(1)

O表达式（Big O notation）通常用来在计算机科学中表示算法的复杂度，包括：

时间复杂度：衡量算法的运行时间

空间复杂度：衡量算法运行所占的空间，比如内存或硬盘等

一般情况下，O表达式代表的是最坏情况下的复杂度。

算法分析也是如此，在n个随即数中查找某个数字，最好的情况是第一个数字就是，此时时间复杂度为O(1)，若最后一个数字才是我们要找的，那么时间复杂度是O(n)，这是最坏的情况。而平均运行时间是从概率的角度看，若数字在每一个位置都可能出现，则平均查找次数为n/2次。

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。即，时间复杂度是最坏情况下的时间复杂度。

常见的算法时间复杂度由小到大依次为：

O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)

这里的O就是一般表示复杂度的一个标志，类似计算复杂度的函数名称一样。

两种复杂度都是一种估算，

估算的方式就是根据代码的逻辑，分析出对于复杂度的公式。

在时间复杂度上，主要记录的是带有变量的循环。

比如for (i = 0; i < n; i ++) {...}可理解为O(n)

而 x = n + 1; y = x + 1; z = x + y;虽然是三条语句，但是没有循环操作，所以理解为O(1)

在空间复杂度上，主要记录的是带有变量的空间申请。

比如int[n] x;可以理解为O(n)

而 int x; int y; int z;虽然是三个变量，但是没有变化的申请操作，所以理解为O(1)

大O符号是用于描述函数渐近行为的数学符号。既可以表示无穷大渐近也可以表示

无穷小渐近。看你是用在算法还是描述数学函数估计中的误差项

再来看看我们的插入排序：

  • 当数组是逆序的时候，时间复杂度是O(n*n）
  • 当数组几乎是有序的时候，时间复杂度是O(n）

另外插入排序的overhead特别小，可以理解为常数等于1

在实际应用中，常数也是一个很重要的因素。有的算法复杂度低，但是常数较高；再加上数据的特点，有时候反而比不上复杂度更高但是常数低的算法。

在理解插入排序算法的过程中，应该要明白一个算法思想：

  • 把问题分解为子问题
  • 找到问题的初始状态
  • 从问题的初始状态，通过子问题，一步步得到最终的解

实际应用中，要灵活的选择算法，有几个重点要考虑的：

  • 复杂度：包括时间复杂度，空间复杂度，常数等
  • 实现复杂度：算法实现起来很难，不易于测试和维护的话，也是很大的问题
  • 适用性：在特定的业务场景下，是否有更合适的算法？

总的来说，要具体情况具体分析，在满足业务的同时要简洁的解决问题。

go 生成区间随机数

// 函　数：生成随机数
// 概　要：
// 参　数：
//  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后台入门】第二课：数组与排序

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • GOLANG版的冒泡排序和快速排序分享

    //冒泡排序 func mpSort(array []int) { for i:=0;i<len(array);i++ { for j:=0;j<len(array)-i-1;j++ { if array[j] > array[j+1] { array[j], array[j+1] = array[j+1], array[j] } } } } //快速排序 func quickSort(array []int, left int, right int) { if left < ri

  • go语言睡眠排序算法实例分析

    本文实例讲述了go语言睡眠排序算法.分享给大家供大家参考.具体分析如下: 睡眠排序算法是一个天才程序员发明的,想法很简单,就是针对数组里的不同的数开多个线程,每个线程根据数的大小睡眠,自然睡的时间越长的,数越大,哈哈,搞笑吧,这种算法看起来很荒唐,但实际上很天才,它可以充分利用多核cpu进行计算. 复制代码 代码如下: package main import (     "fmt"     "time" ) func main() {     tab := []in

  • 深入理解golang的基本类型排序与slice排序

    前言 其实golang的排序思路和C和C++有些差别. C默认是对数组进行排序, C++是对一个序列进行排序, Go则更宽泛一些,待排序的可以是任何对象, 虽然很多情况下是一个slice(分片, 类似于数组),或是包含 slice 的一个对象. 排序(接口)的三个要素: 1.待排序元素个数 n : 2.第 i 和第 j 个元素的比较函数 cmp : 3.第 i 和 第 j 个元素的交换 swap : 乍一看条件 3 是多余的, c 和 c++ 都不提供 swap . c 的 qsort 的用法:

  • 深入解析快速排序算法的原理及其Go语言版实现

    深入解析快速排序算法的原理及其Go语言版实现

    快速排序是一种基于分治技术的重要排序算法.不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分.具体来说,它对给定数组中的元素进行重新排列,以得到一个快速排序的分区.在一个分区中,所有在s下标之前的元素都小于等于A[s],所有在s下标之后的元素都大于等于A[s]. 显然,建立了一个分区以后,A[s]已经位于它在有序数组中的最终位置,接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(使用同样的方法). 为了排序一个数组A的全部元素,初始调用的是QUI

  • Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序 冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码 代码如下:

  • golang使用sort接口实现排序示例

    本文实例讲述了golang使用sort接口实现排序的方法.分享给大家供大家参考,具体如下: 今天看见群里再讨论排序的sort.Interface的实现,有童鞋一直搞不定,我就上手了一下,哦耶搞定了,代码放在这里. 其实很简单sort.Interface借口有三个方法,给自己的struct实现这三个方法,然后用将自己的结构体传给sort.Sort方法就排序完成. 当然sort包也有几个常用的方法sort.Float64Slice sort.IntSlise sort.StringSlise,呵呵

  • Go语言实现选择法排序实例

    本文实例讲述了Go语言实现选择法排序的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import "fmt" func select_sort(a []int) {  len := len(a)  for i:=0; i < len-1; i++ {   k := i   j:= i + 1     for ; j < len; j++ {    if a[j] < a[k] { k = j }   }   if k

  • Go语言使用sort包对任意类型元素的集合进行排序的方法

    本文实例讲述了Go语言使用sort包对任意类型元素的集合进行排序的方法.分享给大家供大家参考.具体如下: 使用sort包的函数进行排序时,集合需要实现sort.Inteface接口,该接口中有三个方法: 复制代码 代码如下: // Len is the number of elements in the collection.  Len() int  // Less reports whether the element with  // index i should sort before t

  • Go语言排序与接口实例分析

    本文实例讲述了Go语言排序与接口用法.分享给大家供大家参考.具体如下: 复制代码 代码如下: import "fmt" type Sorter interface {   Len() int   Less(i, j int) bool   Swap(i, j int) } type Xi []int type Xs []string func (p Xi) Len() int { return len(p) } func (p Xi) Less(i int, j int) bool {

  • Go语言展现快速排序算法全过程的思路及代码示例

    快速排序算法 快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序. 算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大.划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法. 选择最右边的数字作为基数.使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值.然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]

随机推荐