Go 实现洗牌算法
Dyl24H
8年前
<p>shuffle算法,我把它叫做洗牌算法因为他和我们洗扑克牌的方式很像,它的目标正好与各种的sort算法相反,即把一个有序(或者无序)的一系列元素打乱,以满足需求。</p> <p>如果你是python或者ruby程序员可能你觉得很简单,因为他们在语言层面上实现了很多很方便的函数,然而Go语言要想打乱数组或者切片中数据的顺序,需要自己实现的。</p> <p>Ruby中有一个叫shuffle的方法:</p> <pre> <code class="language-objectivec">array = [1, 2, 3, 4, 5] array.shuffle # shuffles the array! </code></pre> <p>Python也同样非常的简单:</p> <pre> <code class="language-objectivec">import random array = [1, 2, 3, 4, 5] random.shuffle(array) # shuffles the array! </code></pre> <h2>简单粗暴 – 创建新的数组或者切片</h2> <pre> <code class="language-objectivec">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 } </code></pre> <p>其实我们可以用 rand.Perm() 更为高效的实现</p> <pre> <code class="language-objectivec">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 } </code></pre> <h2>无需创建新的数组或者切片来实现洗牌算法</h2> <pre> <code class="language-objectivec">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) } } </code></pre> <p>运行后发现你可以看到返回的数据已经被打乱了。</p> <p>如果一个你使用的是切片且不知道切片的大小和容量,且不修改值传递的值,那么我们可以这么做。</p> <pre> <code class="language-objectivec">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] } } </code></pre> <p>Go 实现洗牌算法</p> <p> </p> <p>来自:https://xiequan.info/go-实现洗牌算法/</p> <p> </p>