go实现快速排序，非递归版本

func quickSort(arr []int) []int {
    length := len(arr) - 1
    stack := [][]int{{0, length}}
    for len(stack) > 0 {
        position := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        left := position[0]
        right := position[1]
        index := partition(arr, left, right)
        if left < index - 1 {
            stack = append(stack, []int{left, index-1})
        }
        if right > index + 1 {
            stack = append(stack, []int{index + 1, right})
        }
    }
    return arr
}
func partition(arr []int, left, right int) int {
    indexData := arr[left]
    OUT:
        for left < right {
            for arr[right] >= indexData {
                if left >= right {
                    break OUT
                }
                right--
            }
            arr[left] = arr[right]
            for arr[left] <= indexData {
                if left >= right {
                    break OUT
                }
                left++
            }
            arr[right] = arr[left]
        }
    arr[right] = indexData
    return right
}