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>