Go 语言学习笔记： 快速排序的非递归实现

快速排序就是找出数组的某个值，将数组分为左右两部分，小于该值的放左边大于该值的放右边，再将左右两部分循环执行拆分，直至结束。
例如 1, 11, 9, 7, 5, 6
select = 9
left = [1,7,5,6]
right = [11]
左侧可以继续拆分
select = 7
left = [1,5,6]
right = []
合起来的顺序的变为[[1,5,6], [7], [], [9], [11]]
左侧继续拆分select = 5
left = [1]
right = [6]
合起来的顺序的变为[[1],[5],[6], [7],[] [9], [11]]
至此不可再次拆分。 从底部顺序合并，
1, 5, 6, 7, 9, 11 。
上一层可再分的每次都替换为 进一步拆分的结果。
由此思路使用 golang 进行实现：

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    //首次拆分
    left, selectValue, right := split(arr)
    list := [][]int{left, selectValue, right}
    for i := 0; i < len(list); i++ {
        v := list[i]
        if len(v) <= 1 {
            continue
        }
        A, B, C := split(v)
        temp := make([][]int, len(list[i+1:]))
        copy(temp, list[i+1:])
        //替换长度大于1的
        list = append(append(list[:i], A, B, C), temp...)
        i--
    }
    var result []int
    for _, v := range list {
        if len(v) > 0 {
            result = append(result, v[0])
        }
    }
    return result
}

func split(arr []int) ([]int, []int, []int) {
    selectIndex := len(arr) / 2
    var left, right []int
    for i, v := range arr {
        if selectIndex == i {
            continue
        }
        if v <= arr[selectIndex] {
            left = append(left, v)
            continue
        }
        right = append(right, v)
    }
    return left, []int{arr[selectIndex]}, right
}