开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法-快速排序法】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9852
数据结构和算法-快速排序法
快速排序法介绍：
快速排序(Quicksort)是对冒泡排序的一种改进。
基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序法示意图：
这个图是以最后一个为基准，但并不是每一个都是以最后一个为基准，这个案例是以中间数为中轴，以它为支点进行分割的，如果以11为基准，是从小到大排，它先把比11小的数放在一边，
但是它并不是有序的，它只能把比11小的放在一边，然后比11大的放在11的另一边，因为它是从小到大排，接下来还要分，
它又把11左边的的数，以最后一个数为基准，然后比5小的放在一边，比5大的放在另一边，然后再把右边的分割，
再以最后的数为基准，比8大的分在一边，比8小的分在另一边，因为8左边没有了，所以就不分了，这样2 5 8 10就出来了，同样的方法，11右边的数也是无序的，也像刚才那样分开即可。
所以整个过程就是一个递归的过程，这个理解起来就比选择和插入排序要困难很多了。因为这里用到了很多递归。
应用实例：
要求：对[-9，78，0，23，-567，70]进行从小到大的
排序，要求使用快速排序法。
【测试8 w 和800 w】
说明［验证分析］：
t)如果取消左右遂归，结果是-9 -567 0 23 78 70
2)如果取消右递归，结果是-567 -9 0 23 78 70
3)如果取消左递归，结果是-9 -567 0 23 70 78
代码实现：
package main
import
"fmt"
)
//快速排序
//说明
//1.left 代表数组左边的下标
2.right 表示数组右边的下标
3.array 表示要排序的数组
func quick Sort(left int, right int, array*[6]int){
1:=left
r:=right
//pivot 是一个中轴，也叫支点
pivot:=array[(left+right)/2]把中间的数当做支点
temp s=0
//for 循环的目标是将比 pivo t小的数放到左边
//把 pivot 大的数放在右边
for;1<r;{
//先从 pivot 的左边找到大于等于 pivot 的值
要不停的找
for;array[1]<pivot;{
L++
)
//再从 pivot 的右边找到小于等于 pivot 的值
for;array[r]>pivot;{
)
// l>=r表明分解任务完成，针对这一次的
if l>=r{
break
}
//交换，其实就是78和-567交换，位置互换
temp=array[l]
array[l]=array[r]
array[r]=temp
//优化
if array[l]==pivot{
r--
}
if array[r]==pivot{
L++
//如果 l==r,再移动一位
if l==r{
L++
R--
//向左递归
If left<r{
quicksort(left,r, array)
}
//向右递归
if right >1{
quicksort(1, right, array)
}
}
func main(){
arr;=[6]int{-9，78，0，23，-567，70}
//调用快速排序
Quicksort（0，len(arr)-1,&arr)
Fmt.println(“main...”)
Fmt.println(arr)
}
现在要理解成两个指针，一个左边的指针，一个右边的指针，现在它先找到中间的那个值，也就是现在 pivot 就是0，就相当于找到那个值78，找到78的目标就是再找到右边一个比78小的数交换，两者交换。
显然还有一个指针，要找到小于0的就是-567，找不到就一直找，一直找不到说明已经达到目的了，就不用再找了，整个for循环结束之后，左右就都找到了，把下边的都注销后就会发现是正确的,接下来调用快速排序。
效果和我们分析的是一样的，所以它在0的左边也不是从小到大的，在0的右边也不是从小到大的，所以我们注销的代码是必不可少的。它就能保证0左边和右边的递归是正确的。
如果代码没有变化，0左边还是没有递归的，也不是从小到大排的。处理过后就保证了0左右两边都是有序的。
现在把数据量扩大一点，结果还是正确的。
func quick Sort(left int, right int, array*[9]int){
1:=left
r:=right
//pivot 是一个中轴，也叫支点
pivot:=array[(left+right)/2]把中间的数当做支点
temp s=0
//for 循环的目标是将比 pivot 小的数放到左边
//把 pivot 大的数放在右边
for;1<r;{
//先从 pivot 的左边找到大于等于 pivot 的值
要不停的找
for;array[1]<pivot;{
L++
)
//再从 pivot 的右边找到小于等于 pivot 的值
for;array[r]>pivot;{
)
// l>=r表明分解任务完成，针对这一次的
if l>=r{
break
}
//交换，其实就是78和-567交换，位置互换
temp=array[l]
array[l]=array[r]
array[r]=temp
//优化
if array[l]==pivot{
r--
}
if array[r]==pivot{
L++
//如果 l==r,再移动一位
if l==r{
L++
S--
//向左递归
If left<r{
quicksort(left,r, array)
}
//向右递归
if right >1{
quicksort(1, right, array)
}
}
func main(){
arr;=[9]int{-9，78，0，23，-567，70，123，90，-23}
//调用快速排序
Quicksort（0，len(arr)-1,&arr)
Fmt.println(“main...”)
Fmt.println(arr)
}
增加之后会发现是正确的，是从小到大排的。
