package main

import (

    "fmt"

)

func main() {

    arr := []int{11, 8, 3, 9, 7, 1, 2, 5}

    n := len(arr)

    // newArr := insertionSort(arr, n)

    // newArr := bubbleSort(arr, n)

    // newArr := mergeSort(arr, n)

    newArr := quickSort(arr, n)

    fmt.Println(newArr)

}

// 冒泡

func bubbleSort(arr []int, n int) []int {

    if n <= 1 {

        return arr

    }

    for i := 0; i < n; i++ {

        flag := false

        for j := 0; j < n-1-i; j++ {

            if arr[j] > arr[j+1] {

                arr[j], arr[j+1] = arr[j+1], arr[j]

                flag = true

            }

        }

        if !flag {

            break

        }

        fmt.Print(flag)

        fmt.Println(arr)

    }

    return arr

}

//插入排序

func insertionSort(arr []int, n int) []int {

    if n <= 1 {

        return arr

    }

    for i := 1; i < n; i++ { //外層循環(huán)控制每次需要插入的數(shù)

        j := i

        val := arr[i]      //這次循環(huán)需要加入的數(shù)

        for ; j > 0; j-- { //內(nèi)層循環(huán)遍歷排好序的一側(cè)

            // //類似冒泡排序，交換位置

            // if val < arr[j-1] {//小于則交換位置

            //     arr[j], arr[j-1] = arr[j-1], arr[j]

            // }

            //整體位移，找到位置后賦值

            if val < arr[j-1] {

                arr[j] = arr[j-1]

            } else {

                break

            }

        }

        arr[j] = val

    }

    return arr

}

//選擇

//歸并排序

func mergeSort(arr []int, n int) []int {

    mergeSortC(arr, 0, n-1)

    return arr

}

//歸并函數(shù)

func mergeSortC(a []int, p, r int) {

    //終止條件

    if p >= r {

        return

    }

    //取pr中間值q

    q := 0

    if (r-p+1)%2 == 0 {

        q = (p + r - 1) / 2

    } else {

        q = (p + r) / 2

    }

    //分治遞歸

    mergeSortC(a, p, q)

    mergeSortC(a, q+1, r)

    //合并

    merge(a, p, r, q)

}

func merge(a []int, p, r, q int) {

    i := p

    j := q + 1

    k := 0

    tem := make([]int, len(a))

    for i <= q && j <= r {

        if a[i] <= a[j] { //穩(wěn)定排序

            tem[k] = a[i]

            k++

            i++

        } else {

            tem[k] = a[j]

            k++

            j++

        }

    }

    //判斷子數(shù)組中是否有剩余

    if i-1 == q {

        //j中存在剩余

        for j <= r {

            tem[k] = a[j]

            k++

            j++

        }

    } else if j-1 == r {

        //i中存在剩余

        for i <= q {

            tem[k] = a[i]

            k++

            i++

        }

    }

    //將tem拷貝回a

    for i := 0; p+i <= r; i++ {

        a[p+i] = tem[i]

    }

}

//快速排序

func quickSort(a []int, n int) []int {

    quickSortC(a, 0, n-1)

    return a

}

func quickSortC(a []int, p, r int) {

    if p >= r {

        return

    }

    q := partition(a, p, r)

    quickSortC(a, p, q)

    quickSortC(a, q+1, r)

}

func partition(a []int, p, r int) int {

    povit := a[r] //取最后一位作為povit,后期優(yōu)化的點(diǎn) 

    i := p

    for j := p; j <= r-1; j++ {

        if a[j] < povit {

            a[j], a[i] = a[i], a[j]//涉及位置交換，不穩(wěn)定

            i++

        }

    }

    if i == r {

        return i - 1

    }

    a[r], a[i] = a[i], a[r]

    return i

}