快速排序-golang

快速排序-golang

package main
import "fmt"

var n int
var arr []int

func main(){
    fmt.Scanf("%d", &n)
    arr = make([]int, n)
    for i := 0; i < n; i ++{
        fmt.Scanf("%d", &arr[i])
    }

    quickSort(arr, 0, n-1)

    for i := 0; i < n; i++{
        fmt.Printf("%d ", arr[i])
    }
}

func quickSort(arr []int, left, right int){
    if left >= right{
        return
    }

    mid := arr[(left+right+1)>>1]

    l := left -1
    r := right+1

    for l < r{
        for {
            l++
            if arr[l] >= mid{
                break
            }
        }

        for{
            r--
            if arr[r] <= mid {
                break
            }
        }
        if l <r{
            arr[l], arr[r] = arr[r], arr[l]
        }
    }

    quickSort(arr, left, l-1)
    quickSort(arr, l, right)
}