Go 實現洗牌算法

shuffle算法，我把它叫做洗牌算法因為他和我們洗撲克牌的方式很像，它的目標正好與各種的sort算法相反，即把一個有序(或者無序)的一系列元素打亂，以滿足需求。

如果你是python或者ruby程序員可能你覺得很簡單，因為他們在語言層面上實現了很多很方便的函數，然而Go語言要想打亂數組或者切片中數據的順序，需要自己實現的。

Ruby中有一個叫shuffle的方法：

array = [1, 2, 3, 4, 5]  
array.shuffle # shuffles the array!

Python也同樣非常的簡單：

import random  
array = [1, 2, 3, 4, 5]  
random.shuffle(array) # shuffles the array!

簡單粗暴 – 創建新的數組或者切片

func Shuffle(vals []int) []int {  
  r := rand.New(rand.NewSource(time.Now().Unix()))
  ret := make([]int, len(vals))
  n := len(vals)
  for i := 0; i < n; i++ {
    randIndex := r.Intn(len(vals))
    ret[i] = vals[randIndex]
    vals = append(vals[:randIndex], vals[randIndex+1:]...)
  }
  return ret
}

其實我們可以用 rand.Perm() 更為高效的實現

func Shuffle(vals []int) []int {  
  r := rand.New(rand.NewSource(time.Now().Unix()))
  ret := make([]int, len(vals))
  perm := r.Perm(len(vals))
  for i, randIndex := range perm {
    ret[i] = vals[randIndex]
  }
  return ret
}

無需創建新的數組或者切片來實現洗牌算法

func main() {  
  vals := []int{10, 12, 14, 16, 18, 20}
  r := rand.New(rand.NewSource(time.Now().Unix()))
  for _, i := range r.Perm(len(vals)) {
    val := vals[i]
    fmt.Println(val)
  }
}

運行后發現你可以看到返回的數據已經被打亂了。

如果一個你使用的是切片且不知道切片的大小和容量，且不修改值傳遞的值，那么我們可以這么做。

func Shuffle(vals []int) {  
  r := rand.New(rand.NewSource(time.Now().Unix()))
  for len(vals) > 0 {
    n := len(vals)
    randIndex := r.Intn(n)
    vals[n-1], vals[randIndex] = vals[randIndex], vals[n-1]
    vals = vals[:n-1]
  }
}

Go 實現洗牌算法

來自：https://xiequan.info/go-實現洗牌算法/