目录
1. hoare法
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，我们先来介绍的就是他所创建的方法。
方法步骤：
1. 选择数组最左边(最右边)为基准数key
2. 从右边开始(从左边)开始进行筛选，右边(从左边)选出小于key的数
3. 然后从左边(从右边)开始选择出大于key的数
4. 两者进行交换
5. 重复上述循环，直到左边和右边相遇
这里有个难点：为什么选取左边为基准数就要从右边开始寻找？
因为从右边开始可以保证最后相遇处的数是小于key的，这样才满足最终结果：左边都小于key，右边都大于key
代码实现如下：
void swap(int*a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
//hoare版本
int Partition2(int*a,int left,int right){
int key=left; //从最左边开始
while(left<right){
//先从右边开始找
while(left<right&&a[right]>=a[key]){//找到右边的小于a[key]的值
right--;
}
while(left<right&&a[left]<=a[key]){ //找到左边的大于a[key]的值
left++;
}
swap(a,left,right); //找到了就交换
}
swap(a,left,key); //最后基准数和相遇点进行交换，返回相遇点
return left;
}
void QuickSort(int*a,int left,int right){
if(right<=left){ //数组中只有一个元素，或者不存在该数组
return;
}
//单趟排序后pivot就是最终确定的位置
int pivot=Partition3(a,left,right);
//利用分治的思想
QuickSort(a,left,pivot-1);
QuickSort(a,pivot+1,right);
}2.? 挖坑法
挖坑法是快速排序的一种更新版。
实现步骤：
1. 以最左边为基准数key，并保留其数据。
2. 可以视基准数的位置空出来了，那从最右边开始寻找小于key的数放置在此坑位上。
3. 当从右边找到合适的数放置左边的坑位时，那右边就多了一个坑位，然后就从左边开始找一个大于key的数放在此坑位。
4. 重复上述步骤，直到最终左边和右边相遇。
代码实现：
void swap(int*a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int Partition(int*a,int left,int right){
//挖坑法
int key=a[left];
//挖坑
int pit=left; //开始选择坑位left
while(left<right){
while(left<right&&a[right]>=key){ //找到小于key的数
right--;
}
if(left<right){
a[pit]=a[right];//填在坑位上
pit=right; //坑位变成right位置
}
while(left<right&&a[left]<=key){ //找到大于key的数
left++;
}
if(left<right){ //同理
a[pit]=a[left];
pit=left;
}
}
a[pit]=key; //最后的坑位就是left==right的位置
return pit;
}?使用了局部变量pit让代码更有可读性，那精简版是什么？
//快速排序
int Partition(int*a,int left,int right){
//挖坑法
int key=a[left];
while(left<right){
while(left<right&&a[right]>=key){
right--;
}
if(left<right){
a[left]=a[right]
}
while(left<right&&a[left]<=key){
left++;
}
if(left<right){
a[right]=a[left]
}
}
a[left]=key;
return left;
}这里舍去了pit变量，代码更加简洁。
3. 前后指针法
与挖坑法相同也是一种更新版本。
实现步骤：
1. 使用指针prev指向第一个位置，指针cur指向下一个位置。
2. 当cur所指的数据不小于key时，cur指针后移
3. 当cur所指的数据小于key，prev指针后移并与cur指针进行数据交换，然后cur后移。
4. 重复上述操作，直到cur超出界限。
代码实现如下：
void swap(int*a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int Partition3(int*a,int left,int right){
int key=a[left];//基准数
int prev=left;//指向第一位
int cur=1+left;//指向下一个位置
int temp=0;
while(cur<=right){
//如果prev紧邻cur，交换无意义
if(a[cur]<key&&a[++prev]!=a[cur]){
swap(a,cur,prev);
}
cur++; //cur后移
}
swap(a,left,prev);//交换prev和left的位置
return prev;//返回prev
}为什么当cur小于key还要保证prev+1!=cur才进行交换呢？
因为当prev紧邻cur时，则说明两个指针之间没有大于key的数据，无需进行自我交换
当prev+1!=cur时，则说明两个指针之间有大于key的数据，当prev+1则找到了大于key的数，跟cur所指小于key的数进行交换则满足了小于key的在左边，大于key的在右边。
直到cur大于right,则说明之后没有小于key的数，则将prev与left进行交换，完成小于key的在左边，大于key的在右边。
