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