package main

import (
    "fmt"
    "math/rand"
)

func main() {
    nums := []int{1, 5, 1, 1, 6, 4}
    wiggleSort(nums)
    fmt.Println(nums)
}

// 时间复杂度O(N)，额外空间复杂度O(1)
func wiggleSort(nums []int) {
    if len(nums) < 2 {
        return
    }
    N := len(nums)
    // 小 中 右
    findIndexNum(nums, 0, len(nums)-1, N/2)
    if (N & 1) == 0 {
        // R L -> L R
        shuffle(nums, 0, len(nums)-1)
        // R1 L1 R2 L2 R3 L3 R4 L4
        // L4 R4 L3 R3 L2 R2 L1 R1 -> 代码中的方式，可以的！
        // L1 R1 L2 R2 L3 R3 L4 R4 -> 课上的分析，是不行的！不能两两交换！
        reverse(nums, 0, len(nums)-1)
        // 做个实验，如果把上一行的code注释掉(reverse过程)，然后跑下面注释掉的for循环代码
        // for循环的代码就是两两交换，会发现对数器报错，说明两两交换是不行的, 必须整体逆序
        //          for (int i = 0; i < nums.length; i += 2) {
        //              swap(nums, i, i + 1);
        //          }
    } else {
        shuffle(nums, 1, len(nums)-1)
    }
}

func findIndexNum(arr []int, L int, R int, index int) int {
    pivot := 0
    var range2 []int
    for L < R {
        //pivot = arr[L+(int)(Math.random()*(R-L+1))]
        pivot = arr[L+rand.Intn(R-L+1)]
        range2 = partition(arr, L, R, pivot)
        if index >= range2[0] && index <= range2[1] {
            return arr[index]
        } else if index < range2[0] {
            R = range2[0] - 1
        } else {
            L = range2[1] + 1
        }
    }
    return arr[L]
}

func partition(arr []int, L int, R int, pivot int) []int {
    less := L - 1
    more := R + 1
    cur := L
    for cur < more {
        if arr[cur] < pivot {
            less++
            //swap(arr, ++less, cur++);
            arr[less], arr[cur] = arr[cur], arr[less]
            cur++
        } else if arr[cur] > pivot {
            more--
            //swap(arr, cur, --more);
            arr[more], arr[cur] = arr[cur], arr[more]
        } else {
            cur++
        }
    }
    return []int{less + 1, more - 1}
}

func shuffle(nums []int, l int, r int) {
    for r-l+1 > 0 {
        lenAndOne := r - l + 2
        bloom := 3
        k := 1
        for bloom <= lenAndOne/3 {
            bloom *= 3
            k++
        }
        m := (bloom - 1) / 2
        mid := (l + r) / 2
        rotate(nums, l+m, mid, mid+m)
        cycles(nums, l-1, bloom, k)
        l = l + bloom - 1
    }
}

func cycles(nums []int, base int, bloom int, k int) {
    for i, trigger := 0, 1; i < k; i, trigger = i+1, trigger*3 {
        next := (2 * trigger) % bloom
        cur := next
        record := nums[next+base]
        tmp := 0
        nums[next+base] = nums[trigger+base]
        for cur != trigger {
            next = (2 * cur) % bloom
            tmp = nums[next+base]
            nums[next+base] = record
            cur = next
            record = tmp
        }
    }
}

func rotate(arr []int, l int, m int, r int) {
    reverse(arr, l, m)
    reverse(arr, m+1, r)
    reverse(arr, l, r)
}

func reverse(arr []int, l int, r int) {
    for l < r {
        arr[l], arr[r] = arr[r], arr[l]
        l++
        r--
    }
}