快速排序算法的思路分两部分：
1：在一个线性表中，找到一个基准数据用tmp表示，然后将比tmp大的数据全部放在它的右边，比tmp小的数据放在 它的左边，其实就是快速找出tmp在线性表中正确的下标位置:。
2：将线性表以tmp的下标 分为左右两部分，再分别找出左右两部分的第一个位置的元素的正确的下标，重复上面的分而治之的思路，最终线性表所有元素都找到其正确的位置，那么也就实现了排序
package ds
import "log"
//将线性表s中，i下标的值s[i]按照从从小到大的顺序放到正确的位置
//寻找s[i]在线性表s中按照一定顺序(由小到大)所对应的正确的位置,并返回排序后新的基准下标值
//r表示线性表的最大下标的分界线
func ajustLinear(s []int, i, r int) int {
//用tmp代表s[i]的值
tmp := s[i]
for i < r {
//从线性表右边向左寻找比tmp小的数据，存放到位置i后，基准点 i++
for i < r && s[r] > tmp {
r--
}
if i < r {
s[i] = s[r]
i++
}
//从线性表左边向右边寻找比tmp大的数据，存放到r位置，r--
for i < r && s[i] < tmp {
i++
}
if i < r {
s[r] = s[i]
r--
}
}
//当i向右移动，r向左移动满足 i==r时候，tmp基准值在s的正确下标就是i，将tmp赋值给s[i]，并返回新的基准点i
s[i] = tmp
log.Printf("排序后的线性表:%v",s)
return i
}
//分治算法实现快速排序,
func QuickSort(s []int,i,r int) {
if i<r {
//首次找到基准数据的正确位置后
t := ajustLinear(s, i, r)
//将线性表分为左右两半，继续递归查找基准数据的正确位置
QuickSort(s,i,t-1)
QuickSort(s,t+1,r)
}
}
以下是测试结果:
微信图片_20200701105057.png
ps:类似这种分治的算法也可以用在二叉树的遍历上，重在干净整洁一目了然的演示算法，不严谨的地方暂时忽略
