func MySort( arr []int ) []int {
    // 冒泡
    // 大的往后冒
    for i := 0; i < len(arr); i++{
        for j := 0; j < len(arr) - 1 - i; j++ {
            if arr[j] > arr[j + 1]{
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            }
        }
    }
    return arr
}

func MySort( arr []int ) []int {
    // 小的往前冒
    for i := 0; i < len(arr); i++{
        for j := len(arr) - 1; j > i ; j-- {
            if arr[j] < arr[j - 1]{
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            }
        }
    }
    return arr
}

func MySort( arr []int ) []int {
    // 选择排序
    // 不稳定：5 5 1
    for i := 0; i < len(arr); i++{
        minPoi := i
        for j := i + 1; j < len(arr); j++{
            if arr[minPoi] > arr[j] {
                minPoi = j
            }
        }
        arr[i], arr[minPoi] = arr[minPoi], arr[i]
    }
}

func MySort( arr []int ) []int {
    // 稳定：2 2 1
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i - 1]{
            temp := arr[i]
            j := i - 1
            for j >= 0 && temp < arr[j] {
                arr[j + 1] = arr[j]
                j--
            }
            arr[j + 1] = temp
        }
    }
}

func MySort( arr []int ) []int {
    // 不稳定：相同元素不在同一组，则无法保证相对顺序
    var shell func(int, int)
    shell = func(begin, step int) {
        for i := begin + step; i < len(arr); i += step {
            if arr[i] < arr[i - step] {
                temp := arr[i]
                j := i - step
                for j >= begin && temp < arr[j] {
                    arr[j + step] = arr[j]
                    j -= step
                }
                arr[j + step] = temp
            }
        }
    }
    step := len(arr)/2
    for step > 0 {
        for i := 0; i < step; i++{
            shell(i, step)
        }
        step /= 2
    }
}

func MySort( arr []int ) []int {
    // 2 2 1 稳定
    if len(arr) < 2 {
        return arr
    }
    mid := len(arr)/2
    left := arr[:mid]
    right := arr[mid:]
    var merge func([]int, []int) []int
    merge = func(left []int, right []int)(ans []int){
        i := 0
        j := 0
        for i < len(left) && j < len(right){
            if left[i] <= right[j] {
                ans = append(ans, left[i])
                i++
            }else{
                ans = append(ans, right[j])
                j++
            }
        }
        ans = append(ans, left[i:]...)
        ans = append(ans, right[j:]...)
        return
    }
    return merge(MySort(left), MySort(right))
}

func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 2,2,1 不稳定
    var quicSort func(int, int)
    quicSort = func(begin, end int) {
        if(end - begin <= 0){
            return
        }
        cur := arr[begin]
        left := begin
        right := end
        isRight := true
        for left != right {
            if isRight {
                if arr[right] < cur {
                    arr[left] = arr[right]
                    isRight = !isRight
                }else{
                    right--
                }
            } else {
                if arr[left] > cur {
                    arr[right] = arr[left]
                    isRight = !isRight
                }else{
                    left++
                }
            }
        }
        arr[left] = cur
        quicSort(begin, left - 1)
        quicSort(left + 1, end)
    }
    quicSort(0, len(arr) - 1)
}

func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 不稳定 2 2 1
    // 从小到大排序，用大顶堆，每次把根节点放最后，然后end - 1
    var down func(int, int) 
    down = func(start int, end int){
        for start < end {
            fmt.Println(start)
            left := 2 * start + 1
            right := 2 * start + 2
            if left > end {
                break
            }
            max := arr[left]
            if right <= end && arr[right] > max{
                max = arr[right]
            }
            if max > arr[start] {
                if max == arr[left] {
                    arr[start], arr[left] = arr[left], arr[start]
                    start = left
                } else {
                    arr[start], arr[right] = arr[right], arr[start]
                    start = right
                }
            }else{
                break
            }
        }
    }
    end := len(arr) - 1
    // 先建堆
    // end的父节点是：(end - 1)/2
    for i := (end - 1)/2; i >= 0; i-- {
        down(i, end)
    }
    fmt.Println(arr[end])
    // 再排序
    for end >= 1 {
        arr[0], arr[end] = arr[end], arr[0]
        end--
        down(0, end)
    }
}

func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    minArr := math.MaxInt
    maxArr := -1
    for _, v := range arr {
        if minArr > v {
            minArr = v
        }
        if maxArr < v {
            maxArr = v
        }
    }
    record := make([]int, maxArr - minArr + 1)
    for _, v := range arr {
        record[v - minArr]++
    }
    cur := 0
    for i, v := range record {
        for v > 0 {
            arr[cur] = i + minArr
            cur++
            v--
        }
    }
}

func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 找到最大值
    maxValue := -1
    for _, v := range arr {
        if maxValue < v {
            maxValue = v
        }
    }
    // 找到最高位
    maxBit := 0
    for maxValue != 0 {
        maxValue /= 10
        maxBit++
    }
    // fmt.Println(maxBit)
    // 声明十个桶
    buckets := make([][]int, 10)
    base := 1
    for i := 0; i < maxBit; i++ {
        for _, v := range arr {
            buckets[(v / base) % 10] = append(buckets[(v/base)%10], v)
        }
        index := 0
        for j, bucket := range buckets {
            if len(bucket) == 0 {
                // fmt.Println(len(bucket))
                continue
            }
            for _, v := range bucket{
                arr[index] = v
                index++
            }
            // 清空桶
            buckets[j] = buckets[j][:0]
        }
        base *= 10
    }
    return arr
}