快速排序
最后更新于：2022-04-02 04:11:02
[TOC]
## 示例
```
func QuickSort(nums []int) []int {
// 思路：把一个数组分为左右两段，左段小于右段，类似分治法没有合并过程
quickSort(nums, 0, len(nums)-1)
return nums
}
// 原地交换，所以传入交换索引
func quickSort(nums []int, start, end int) {
if start < end {
// 分治法：divide
pivot := partition(nums, start, end)
quickSort(nums, 0, pivot-1)
quickSort(nums, pivot+1, end)
}
}
// 分区
func partition(nums []int, start, end int) int {
p := nums[end]
i := start
for j := start; j < end; j++ {
if nums[j] < p {
swap(nums, i, j)
i++
}
}
// 把中间的值换为用于比较的基准值
swap(nums, i, end)
return i
}
func swap(nums []int, i, j int) {
t := nums[i]
nums[i] = nums[j]
nums[j] = t
}
```
';