前言
排序，對于每種編程語言都是要面對的。這里跟大家一起分享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后臺入門】第二課：數組與排序
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。
您可能感興趣的文章:- Go語言實現冒泡排序、選擇排序、快速排序及插入排序的方法
- Golang 實現插入排序的方法示例(2種)
