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

前言

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

經(jīng)典排序算法

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

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

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

插入排序

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

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

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

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

具體實(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ù)雜度：

時(shí)間復(fù)雜度：O(n*n）

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

O表達(dá)式（Big O notation）通常用來(lái)在計(jì)算機(jī)科學(xué)中表示算法的復(fù)雜度，包括：

時(shí)間復(fù)雜度：衡量算法的運(yùn)行時(shí)間

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

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

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

平均運(yùn)行時(shí)間是所有情況中最有意義的，因?yàn)樗瞧谕倪\(yùn)行時(shí)間。可現(xiàn)實(shí)中，平均運(yùn)行時(shí)間很難通過(guò)分析得到，一般都是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算而來(lái)的。而最壞運(yùn)行時(shí)間是一種保證，那就是運(yùn)行時(shí)間不會(huì)再壞了。在應(yīng)用中，這是最重要的需求，通常，除非特別指定，我們提到的運(yùn)行時(shí)間都是最壞情況下的運(yùn)行時(shí)間。即，時(shí)間復(fù)雜度是最壞情況下的時(shí)間復(fù)雜度。

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

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

這里的O就是一般表示復(fù)雜度的一個(gè)標(biāo)志，類似計(jì)算復(fù)雜度的函數(shù)名稱一樣。

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

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

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

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

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

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

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

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

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

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

再來(lái)看看我們的插入排序：

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

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

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

在理解插入排序算法的過(guò)程中，應(yīng)該要明白一個(gè)算法思想：

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

實(shí)際應(yīng)用中，要靈活的選擇算法，有幾個(gè)重點(diǎn)要考慮的：

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

總的來(lái)說(shuō)，要具體情況具體分析，在滿足業(yè)務(wù)的同時(shí)要簡(jiǎn)潔的解決問(wèn)題。

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

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

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

總結(jié)

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