package main

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

func main() {
    rand.Seed(time.Now().Unix())
    sucCount := 0
    failedCount := 0
    for i := 0; i < 2000; i++ {
        arr1 := GenRandArr()
        arr2 := make([]int, len(arr1))
        fmt.Println("原数组：", arr1)
        copy(arr2, arr1)
        BubbleSort(arr1)
        QuickSort(arr2)
        fmt.Println("冒泡排序", arr1)
        fmt.Println("快速排序", arr2)
        fmt.Println("--------")
        if IsEqual(arr1, arr2) {
            sucCount++
        } else {
            failedCount++
        }
    }
    fmt.Println("成功：", sucCount)
    fmt.Println("失败：", failedCount)

}

//荷兰国旗问题三分
func partition(arr []int, val int) (int, int) {
    lessEqual := -1
    moreEqual := len(arr)
    index := 0
    for index < moreEqual {
        if arr[index] < val { //左区右扩
            lessEqual++
            arr[index], arr[lessEqual] = arr[lessEqual], arr[index]
            index++
        } else if arr[index] > val { //右区左扩，注意index不会++
            moreEqual--
            arr[index], arr[moreEqual] = arr[moreEqual], arr[index]
        } else { //相等区
            index++
        }
    }
    return lessEqual, moreEqual
}

//三分随机快排递归
func QuickSort(arr []int) {
    arrLen := len(arr)
    if arrLen < 2 {
        return
    }
    //荷兰国旗问题三分，以数组中的随机1个元素划分
    left, right := partition(arr, arr[rand.Intn(arrLen)])
    //左边快排
    QuickSort(arr[0 : left+1])
    //右边快排
    QuickSort(arr[right:])
}

//for test
func GenRandArr() []int {
    ret := make([]int, rand.Intn(20)+10)
    retLen := len(ret)
    for i := 0; i < retLen; i++ {
        ret[i] = rand.Intn(100)
    }
    return ret
}

//for test
func BubbleSort(arr []int) {
    arrLen := len(arr)
    if arrLen < 2 {
        return
    }
    for i := 0; i < arrLen-1; i++ {
        for j := 0; j < arrLen-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

//for test
func IsEqual(arr1 []int, arr2 []int) bool {
    arr1Len := len(arr1)
    for i := 0; i < arr1Len; i++ {
        if arr1[i] != arr2[i] {
            return false
        }
    }
    return true
}