期望为线性时间的选择算法（golang实现）

介绍一种解决选择问题的分治算法。randonmizedSelect算法以随机版快排为模型。与快排的区别为：

快排会递归处理划分的两边，而此算法只处理划分的一边。

快排期望运行时间为O(nlgn)，此算法的期望运行时间为O(n)。这里假设输入数据都是互异的。

此算法返回数组A[p..r]中第i小的元素。

package main

import (
	"math/rand"
	"time"
)


func partition(arr []int, p, r int) int {
	x := arr[r]
	i := p-1
	for j := p; j < r; j++ {
		if arr[j] < x {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[r] = arr[r], arr[i+1]
	return i+1
}


// 产生在min和max之间的随机数
func RandInt64(min, max int64) int64 {
	rand.Seed(time.Now().UnixNano())
	return min+rand.Int63n(max-min+1)
}

// 随机化的partition
func randomizedPartition(arr []int, p, r int)  int {
	i := int(RandInt64(int64(p), int64(r)))
	arr[r], arr[i] = arr[i], arr[r]
	res := partition(arr, p, r)
	return res
}

// 随机选择算法 
func randomizedSelect(arr []int, p, r, i int) int {
	if p == r {
		return arr[p]
	}
	q := randomizedPartition(arr, p, r)
	k := q-p+1

	if i == k {
		return arr[q]
	} else if i < k {
		return randomizedSelect(arr, p, q-1, i)
	} else {
		return randomizedSelect(arr, q+1, r ,i-k)
	}
}

func main() {
	var arr = []int{2,3,4,1,0,5,6,9,8,7}
	target := 4
	ans := randomizedSelect(arr,0,len(arr)-1,target)
	println(ans)
}