算法(2): 排序

2.1 快速排序

题目描述：实现快速排序

思路：采用交换法，选第一个数为基准数pivot，在pl <= pr的前提下，指针pl从基准数+1的位置向右走，直到碰到比pivot大的数，指针pr从最右边向左走，直到碰到比pivot小的数，交换arr[pl], arr[pr]，循环结束时pr = pl - 1，将基准数和pr交换。递归调用对基准数位置两边的区间调整。

示例代码：

func partition(arr []int, left, right int) int {
    pivot := arr[left]
    pl, pr := left + 1, right
    for pl <= pr {
        for ; pl <= pr && arr[pl] < pivot; pl++ {}
        for ; pl <= pr && arr[pr] > pivot; pr-- {}
        if pl < pr {
            arr[pl], arr[pr] = arr[pr], arr[pl]
        }
    }
    // 结束时pr = pl -1
    arr[left], arr[pr] = arr[pr], arr[left]
    return pr
}

func recursive(arr []int, left, right int)  {
    if left >= right {
        return
    }
    mid := partition(arr, left, right)
    recursive(arr, left, mid - 1)
    recursive(arr, mid + 1, right)
}

func QuickSort(arr []int) []int {
    recursive(arr, 0, len(arr) - 1)
    return arr
}