坚持看完，结尾有思维导图总结

这里写目录标题

• 什么是快排？
• • 如何实现递归
  • • 单次的排序要如何实现
    • • hore 的办法
      • 坑位法
      • 双指针法
  • 总结

什么是快排？

首先按照官方定义:
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

按照官方的定义我们看不出来什么
但是如果我们用图示的方式演示一下就能够明白
假设有一个序列 :
572136，通过单趟排序，每个数组的第一个能够找到对应的位置，同时保证这个数的左边都是比他小的数，右边都是比他大的数

排序后 ，5 的左边都是比5小的数，5的右边都是比5大的数
然后以五位分界线，将数组分为左数组和右数组，执行相同的排序

黑色的是分段
红色的是分段后回到原数组

如何实现递归

递归有两个要素，得到最后数据的位置
按照最后数据的位置切分数组

void QuickSort(int* a ,int begin,int end)
{if(end - begin +1 <= 1)//只有一个元素的时候退出return;int k = PartSort(a,begin,end);QuickSort(a,begin,k-1);QuickSort(a,k+1,end);
}

单次的排序要如何实现

一共有三种方式实现

hore 的办法

有一个要验证的问题，如何保证最后相遇的地方保证比数据小呢？
一共有两种相遇方式，要么是 begin 遇到 end ，要么是end 遇到degin
当 begin 遇到 end 的时候，end 本身是比 key 小的值，所以保证了 遇到的数字比 key 小
当 end 遇到begin ，因为保证了 end 先走，end 行动前， begin 和 end 已经互换，begin 底下就是比 key 小的数，也能保障 相遇的值比 key 小

具体程序

void swap(int*a ,int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
//因为要得到最后的 key的位置，所以要返回 int
int PartSort1(int*a,int begin,int end)
{int key = begin;// 因为尽量不改变 begin 和 end;所以用left 和 right 代替，虽然在函数中也是临时变量int left = begin;int right = end;while(left < right){// right 找到比key 小的值while(right>left && a[right]>=a[key]){right--;}// left 找到比 key 大的值while(leftleft ++ ;}swap(&a[left],&a[right]);}swap(&a[key],&a[right]);return right;} 

程序需要注意的地方

首先要满足 right 总是再后面 left 总是再前面
这样写行不行?

while(right>left && a[right]>a[key])
while(left < right && a[left] < a[key])

再这种情况下， left 和right 始终不会向前走，导致死循环
如果是

while(right>end && a[right]>=a[key])
while(left 

int PartSort2(int* a,int begin,int end)
{int left = begin;int right = end;int pit = begin;//坑位int key = a[left];while(left < right){//right 找小while(right>left && a[right]>=key){right -- ;}// 把小的移动到坑位a[pit] = a[right];pit = right;//left 找大while(leftleft ++ ;}//把大的移动到坑位a[pit] = a[left];pit = left;}a[pit] = key;return pit;}

int PartSort3(int*a,int begin,int end)
{int key = begin;int prev =begin, cur = begin;while(cur <= end){cur ++;//相等直接跳过if(cur<=end && a[cur] < a[key]){prev ++;swap(&a[prev],&a[cur]);}}swap(a+key,a+prev);return prev;
}