Go語言排序算法之如何實現(xiàn)插入排序與生成隨機數(shù)

這篇文章主要為大家展示了“Go語言排序算法之如何實現(xiàn)插入排序與生成隨機數(shù)”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“Go語言排序算法之如何實現(xiàn)插入排序與生成隨機數(shù)”這篇文章吧。

十年的烏海海南網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整烏海海南建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“烏海海南網(wǎng)站設計”,“烏海海南網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

經(jīng)典排序算法

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

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

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

插入排序

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

1.從第1位至第n-1位遍歷數(shù)組，發(fā)現(xiàn)第n位數(shù)字應該放在第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)
}

復雜度：

時間復雜度：O(n*n）

空間復雜度：額外空間O(1)

O表達式（Big O notation）通常用來在計算機科學中表示算法的復雜度，包括：

時間復雜度：衡量算法的運行時間

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

一般情況下，O表達式代表的是最壞情況下的復雜度。

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

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

常見的算法時間復雜度由小到大依次為：

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

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

兩種復雜度都是一種估算，

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

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

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

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

在空間復雜度上，主要記錄的是帶有變量的空間申請。

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

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

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

無窮小漸近。看你是用在算法還是描述數(shù)學函數(shù)估計中的誤差項

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

當數(shù)組是逆序的時候，時間復雜度是O(n*n）
當數(shù)組幾乎是有序的時候，時間復雜度是O(n）

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

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

在理解插入排序算法的過程中，應該要明白一個算法思想：

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

實際應用中，要靈活的選擇算法，有幾個重點要考慮的：

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

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

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 
}

以上是“Go語言排序算法之如何實現(xiàn)插入排序與生成隨機數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁標題：Go語言排序算法之如何實現(xiàn)插入排序與生成隨機數(shù)
標題URL：http://bm7419.com/article0/jdsdio.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供、響應式網(wǎng)站、服務器托管、營銷型網(wǎng)站建設、ChatGPT、小程序開發(fā)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容