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

package main

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

func threeWayParttion(nums []int, target int) {
	nextLess, nextScan, nextLarger := 0, 0, len(nums)-1
	for nextScan <= nextLarger {
		if nums[nextScan] < target {
			swap(nums, nextScan, nextLess)
			nextScan++
			nextLess++
		} else if target < nums[nextScan] {
			swap(nums, nextScan, nextLarger)
			nextLarger--
		} else {
			nextScan++
		}
	}
}

func swap(nums []int, i, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}

func main() {
	var n int
	fmt.Scan(&n)
	nums := make([]int, n)
	rand.Seed(time.Now().Unix())
	for i := range nums {
		nums[i] = rand.Intn(3) + 1
	}
	fmt.Println(nums)
	threeWayParttion(nums, 2)
	fmt.Println(nums)
}