leetcode-go/basis/algorithms/quicksort/quicksort.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type ints []int

func (is ints) less(i, j int) bool { return is[i] < is[j] }
func (is ints) swap(i, j int)      { is[i], is[j] = is[j], is[i] }

func (is ints) getN(n int) int { // Get the Nth smallest number.
	l := len(is)
	lo, hi := 0, l-1
	for lo <= hi {
		m := is.partition(lo, hi)
		if m == n-1 {
			return is[m]
		} else if m < n-1 {
			lo = m + 1
		} else {
			hi = m - 1
		}
	}
	return is[lo]
}

func (is ints) sort() {
	l := len(is)
	rand.Shuffle(l, is.swap)
	is.qsort(0, l-1)
}

func (is ints) qsort(lo, hi int) {
	if hi <= lo {
		return
	}
	m := is.partition(lo, hi)
	is.qsort(lo, m-1)
	is.qsort(m+1, hi)
}

func (is ints) partition(lo, hi int) int {
	i, j := lo, hi+1
	for {
		for i++; is.less(i, lo) && i != hi; i++ {
		}
		for j--; is.less(lo, j) && j != lo; j-- {
		}
		if j <= i {
			break
		}
		is.swap(i, j)
	}
	is.swap(lo, j)
	return j
}

func main() {
	var n int
	fmt.Scan(&n)
	rand.Seed(time.Now().Unix())
	var list ints = make([]int, n)
	for i := range list {
		list[i] = rand.Intn(2 * n)
	}
	fmt.Println(list)
	m := list.getN(n / 2)
	list.sort()
	fmt.Println(list)
	fmt.Println(m, list[n/2-1])
}