一、什么是快速排序？
把一个无序的数组，第一趟排序后将数组分隔成两部分，若把前半部分和后半部分的相交元素称为中间元素。前半部分的所有元素小于中间元素，后半部分的所有元素大于中间元素。再对前半部分和后半部分分别进行上述递归操作。最终得到一个有序数组。
二、如何进行快速排序？
最近正好我在学习Go语言，决定用Go语言自己描述一遍。
func QuickSort(arr []int) {
if len(arr) <= 1 {
return
}
mid, i := arr[0], 1
left, right := 0, len(arr)-1
for left < right {
if arr[i] > mid {
arr[i], arr[right] = arr[right], arr[i]
right--
// 稍微解释一下这里为何不需要 i++
// 因为 arr[right] 和 arr[i] 交换后
// arr[i] 即原来 arr[right] 的值不一定 > mid
// 故下一轮要继续比较
} else {
arr[i], arr[left] = arr[left], arr[i]
left++
i++
// 这里有 i++ 的原因是
// left 的值必然 <= mid
// 交换后只需继续判断 arr[++i]
}
}
arr[left] = mid
QuickSort(arr[:left])
QuickSort(arr[left+1:])
}
但是，上面的代码会存在交换次数过多的问题，这个问题可以使用下面代码进行优化。
func QuickSort(arr []int) {
if len(arr) <= 1 {
return
}
mid := arr[0]
left, right := 0, len(arr)-1
for left < right {
if left < right && arr[right] >= mid {
right--
}
arr[left++] = arr[right]
if left < right && arr[left] <= mid {
left++
}
arr[right--] = arr[left]
}
arr[left] = mid
QuickSort(arr[:left])
QuickSort(arr[left+1:])
}
（如有错误，欢迎指正）
