主頁 > 知識庫 > Go語言排序算法之插入排序與生成隨機數(shù)詳解

Go語言排序算法之插入排序與生成隨機數(shù)詳解

熱門標簽:建造者2地圖標注 惠州電銷防封電話卡 汕頭小型外呼系統(tǒng) 黃岡人工智能電銷機器人哪個好 阿里云ai電話機器人 鄭州亮點科技用的什么外呼系統(tǒng) 濱州自動電銷機器人排名 釘釘有地圖標注功能嗎 浙江高頻外呼系統(tǒng)多少錢一個月

前言

排序,對于每種編程語言都是要面對的。這里跟大家一起分享golang實現(xiàn)一些排序算法,并且說明如何生成隨機數(shù)。下面話不多說了,來一起看看詳細的介紹吧。

經(jīng)典排序算法

算法的學(xué)習(xí)非常重要,是檢驗一個程序員水平的重要標準。學(xué)習(xí)算法不能死記硬背,需要理解其中的思想,這樣才能靈活應(yīng)用到實際的開發(fā)中。

七大經(jīng)典排序算法

  • 插入排序
  • 選擇排序
  • 冒泡排序
  • 希爾排序
  • 歸并排序
  • 堆排序
  • 快速排序

插入排序

先考慮一個問題:對于長度為n的數(shù)組,前n-1位都是遞增有序的,如何排序?

     1.從第1位至第n-1位遍歷數(shù)組,發(fā)現(xiàn)第n位數(shù)字應(yīng)該放在第k位

     2.把第k位至第n-1位的數(shù)字依次向后挪一位

     3.這樣長度為n的數(shù)組就是遞增有序的了

具體實現(xià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)
}

復(fù)雜度:

時間復(fù)雜度:O(n*n)

空間復(fù)雜度:額外空間O(1)

O表達式(Big O notation)通常用來在計算機科學(xué)中表示算法的復(fù)雜度,包括:

時間復(fù)雜度:衡量算法的運行時間

空間復(fù)雜度:衡量算法運行所占的空間,比如內(nèi)存或硬盤等

一般情況下,O表達式代表的是最壞情況下的復(fù)雜度。

算法分析也是如此,在n個隨即數(shù)中查找某個數(shù)字,最好的情況是第一個數(shù)字就是,此時時間復(fù)雜度為O(1),若最后一個數(shù)字才是我們要找的,那么時間復(fù)雜度是O(n),這是最壞的情況。而平均運行時間是從概率的角度看,若數(shù)字在每一個位置都可能出現(xiàn),則平均查找次數(shù)為n/2次。

平均運行時間是所有情況中最有意義的,因為它是期望的運行時間??涩F(xiàn)實中,平均運行時間很難通過分析得到,一般都是通過運行一定數(shù)量的實驗數(shù)據(jù)后估算而來的。而最壞運行時間是一種保證,那就是運行時間不會再壞了。在應(yīng)用中,這是最重要的需求,通常,除非特別指定,我們提到的運行時間都是最壞情況下的運行時間。即,時間復(fù)雜度是最壞情況下的時間復(fù)雜度。

常見的算法時間復(fù)雜度由小到大依次為:

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

這里的O就是一般表示復(fù)雜度的一個標志,類似計算復(fù)雜度的函數(shù)名稱一樣。

兩種復(fù)雜度都是一種估算,

估算的方式就是根據(jù)代碼的邏輯,分析出對于復(fù)雜度的公式。

在時間復(fù)雜度上,主要記錄的是帶有變量的循環(huán)。

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

而 x = n + 1; y = x + 1; z = x + y;雖然是三條語句,但是沒有循環(huán)操作,所以理解為O(1)

在空間復(fù)雜度上,主要記錄的是帶有變量的空間申請。

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

而 int x; int y; int z;雖然是三個變量,但是沒有變化的申請操作,所以理解為O(1)

大O符號是用于描述函數(shù)漸近行為的數(shù)學(xué)符號。既可以表示無窮大漸近也可以表示

無窮小漸近??茨闶怯迷谒惴ㄟ€是描述數(shù)學(xué)函數(shù)估計中的誤差項

再來看看我們的插入排序:

  • 當(dāng)數(shù)組是逆序的時候,時間復(fù)雜度是O(n*n)
  • 當(dāng)數(shù)組幾乎是有序的時候,時間復(fù)雜度是O(n)

另外插入排序的overhead特別小,可以理解為常數(shù)等于1

在實際應(yīng)用中,常數(shù)也是一個很重要的因素。有的算法復(fù)雜度低,但是常數(shù)較高;再加上數(shù)據(jù)的特點,有時候反而比不上復(fù)雜度更高但是常數(shù)低的算法。

在理解插入排序算法的過程中,應(yīng)該要明白一個算法思想:

  • 把問題分解為子問題
  • 找到問題的初始狀態(tài)
  • 從問題的初始狀態(tài),通過子問題,一步步得到最終的解

實際應(yīng)用中,要靈活的選擇算法,有幾個重點要考慮的:

  • 復(fù)雜度:包括時間復(fù)雜度,空間復(fù)雜度,常數(shù)等
  • 實現(xiàn)復(fù)雜度:算法實現(xiàn)起來很難,不易于測試和維護的話,也是很大的問題
  • 適用性:在特定的業(yè)務(wù)場景下,是否有更合適的算法?

總的來說,要具體情況具體分析,在滿足業(yè)務(wù)的同時要簡潔的解決問題。

go 生成區(qū)間隨機數(shù)

// 函 數(shù):生成隨機數(shù) 
// 概 要: 
// 參 數(shù): 
//  min: 最小值 
//  max: 最大值 
// 返回值: 
//  int64: 生成的隨機數(shù) 
func RandInt64(min, max int64) int64 { 
 if min >= max || min == 0 || max == 0 { 
  return max 
 } 
 return rand.Int63n(max-min) + min 
} 

參考文章: 【BAT后臺入門】第二課:數(shù)組與排序

總結(jié)

以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,如果有疑問大家可以留言交流,謝謝大家對腳本之家的支持。

您可能感興趣的文章:
  • Go語言實現(xiàn)冒泡排序、選擇排序、快速排序及插入排序的方法
  • Golang 實現(xiàn)插入排序的方法示例(2種)

標簽:瀘州 滄州 阿壩 東營 昭通 駐馬店 晉中 泰安

巨人網(wǎng)絡(luò)通訊聲明:本文標題《Go語言排序算法之插入排序與生成隨機數(shù)詳解》,本文關(guān)鍵詞  語言,排序,算法,之,插入,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Go語言排序算法之插入排序與生成隨機數(shù)詳解》相關(guān)的同類信息!
  • 本頁收集關(guān)于Go語言排序算法之插入排序與生成隨機數(shù)詳解的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章