快速排序的随机参考元选择

随机选择的伪代码：

1RANDOM-PARTITION (data, left, right)
2    i = RANDOM(left to right)
3    SWAP(data[i], data[right]) 

复制

编码示例

1// go
2func randPartition(data []int, left, right int) int {
3    // 随机索引
4    rand.Seed(time.Now().UnixNano())
5    randI := left + rand.Intn(right-left)
6    // 交互随机元素和末尾元素
7    data[right], data[randI] = data[randI], data[right]
8    return partition(data, left, right)
9}

复制

1# python
2def randPartition(data, left, right):
3  import random
4  randI = random.randint(left, right)
5  data[randI], data[right] = data[right], data[randI]
6  return partition(data, left, right)

复制

1// JavaScript
2function randPartition(data, left, right) {
3    let randI = left + Math.ceil(Math.random()*(right-left))
4    let t = data[right]
5    data[right] = data[randI]
6    data[randI] = t
7    return partition(data, left, right) 
8}

复制

1// PHP，to be continued. 该你了
复制