package sort

/**
快速排序
S = SL + SR
max(SL) <= min(SR)
Sorted(S) = Sorted(SL) + Sorted(SR)
难点在于分
pivot 轴点：(SL) <= pivot <= min(SR) [lo,hi) = [lo,pivot),[pivot],(pivot,hi)
 */
func QuickSort(list []int, start int, end int) {
    //递归基
    if end - start <= 1 {
        return
    }
    pivot := list[start]
    i := start
    j := end-1
    temp := i
    for i < j {
        if temp == i {
            if list[j] < pivot {
                list[temp] = list[j]
                temp = j
                i++
            } else {
                j--
            }
        } else {
            if list[i] > pivot {
                list[temp] = list[i]
                temp = i
                j--
            } else {
                i++
            }
        }
    }
    list[temp] = pivot
    //递归
    QuickSort(list, start, temp)
    QuickSort(list, temp+1, end)
}