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
}