快速排序（动图详解）（C语言数据结构）
快速排序：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序有三个版本，将一一实现。
Hoare版本：
直接上动图理解：
当前为一遍快排。
再分别以key左右两边进行相同的排序
直到key = right = left。
综上得用递归思想。
代码如下：
void QuickSort(int* a, int begin,int end)
{
if (begin >= end)//递归返回条件
{
return;
}
int right = end;
int left = begin;
int key = begin;
while (begin < end)
{
//找小
while (begin<end && a[end]>=a[key])
{
end--;
}
//找大
while (begin<end && a[begin]<=a[key])
{
begin++;
}
swap(&a[begin], &a[end]);
}
swap(&a[key], &a[begin]);
k = begin;
QuickSort(a,left,key-1);//key左边递归
QuickSort(a,key+1,right);//key右边递归
}递归展开图：
优化代码：
通过画递归展开图后，发现如果这个k的取值一直等于left，有缺点，递归的次数较多。
如果能改进就能让效率提高。
改进思路：
如果这个递归能像二叉树一样，总共只需要N*log(N)次，就只需要每次这个k取值去一个中间值，不需要去最大也不需要取最小。
这样的改进方案，称之为三数取中。
像刚刚，如果要递归的话一次需要递归9次，如果每次取中间的值当k，每次只需要递归3次 。
等左边递归结束式左边空间还是可以继续利用的。
代码如下：
int GetMid(int* a, int begin, int end)
{
int mid = (begin+end) / 2;
if (a[mid] > a[end])
{
if (a[mid] < a[begin])
{
return mid;
}
else if (a[end] > a[begin])
{
return end;
}
else
return begin;
}
else
{
if (a[mid] > a[begin])
{
return mid;
}
else if (a[end] < a[begin])
{
return end;
}
else
return begin;
}
}
void QuickSort(int* a, int begin,int end)
{
if (begin >= end)//递归返回条件
{
return;
}
//三数取中
int mid = GetMid(a, begin, end);
swap(&a[mid], &a[begin]);
int right = end;
int left = begin;
int key = begin;
while (begin < end)
{
//找小
while (begin<end && a[end]>=a[key])
{
end--;
}
//找大
while (begin<end && a[begin]<=a[key])
{
begin++;
}
swap(&a[begin], &a[end]);
}
swap(&a[key], &a[begin]);
key = begin;
QuickSort(a,left,key-1);//key左边递归
QuickSort(a,key+1,right);//key右边递归
}挖坑法版本：
代码如下：
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)//递归返回条件
{
return;
}
//三数取中
int mid = GetMid(a, begin, end);
swap(&a[mid], &a[begin]);
int left = begin;
int right = end;
int key = a[left];
int hole = left;//第一个为坑
while (begin < end)
{
//找小
while (begin < end && a[end] >= key)
{
end--;
}
//找到小的后将数据移到刚刚坑位，并将当前位置作为坑
a[hole] = a[end];
hole = end;
//找大
while (begin < end && a[begin] <= key)
{
begin++;
}
//找到大的后将数据移到刚刚坑位，并将当前位置作为坑
a[hole] = a[begin];
hole = begin;
}
a[hole] = key;
QuickSort(a, left, hole - 1);//key左边递归
QuickSort(a, hole + 1, right);//key右边递归
}前后指针法：
cur找小，找到以后prev+1后交换cur和prev。
等cur == n-1之后，将a[key]和a[prev]交换，并且将key = prev。
这个过程保证了prev和cur之间的值是大于key的。
代码如下：
void QuickSort3(int* a, int begin,int end)
{
if (begin>=end)//递归返回条件
{
return;
}
//三数取中
int mid = GetMid(a, begin, end);
swap(&a[mid], &a[begin]);
int prev = begin;
int cur = prev + 1;
int key = prev;
while (cur<=end-begin)
{
if (a[cur] < a[key])
{
prev++;
if (prev < cur)
{
swap(&a[prev],&a[cur]);
}
}
cur++;
}
swap(&a[key], &a[prev]);
key = prev;
QuickSort(a, begin, key - 1);//key左边递归
QuickSort(a, key + 1, end);//key右边递归
}