数据结构——排序3
上次我们讲完了选择排序，堆排序和冒泡排序后，这次我们来讲解一下快速排序。
快速排序又分为Hoare版本，挖坑法，前后指针法，接下来，我们来一一讲解。
首先先基本了解快速排序：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
简单理解就是：
现在给出它的Hoare版本的快速排序动图：
Hoare排序思路:
我们观察动图可以知道，选取了基准值后（一般放到最左边的位置），先让右边先出发。
右边的任务是寻找比基准值小的数，找到后就停。
轮到左边，左边的任务是寻找比基准值大的数，找到就停。
若此时，left和right还为相遇，就交换left和right的数。
再继续按照上面的寻找。直到相遇（left==right），就停止寻找，最后交换key的值和相遇的位置值。
这样就可以分成两部分：一部分比基准值小，一部分比基准值大。
接着继续按照这种思路，把剩下的同样完成。
错误点分析 代码：
void QuickSort(int* a, int left,int right)
{
int keyi = left;
left++；
while (left<right)
{
while (a[right] > a[keyi])
right--;
while (a[left] < a[keyi])
left++;;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
}错误1.
有人按照上面的思路，会写出上面的代码。但是这是有问题的：
如果是上面的这种情况，当出现多个与基准值一样的数时，我们没有让它等于时进入循环 发现它会出现死循环，所以要加上=
while (a[right] >= a[keyi])
right--;
while (a[left] <= a[keyi])
left++;;
错误2 ：
上面情况下，你会发现会发生错误了。所以还要加上 这样的条件：
while (left<right && a[right] >= a[keyi])
right--;
while (left<right && a[left] <= a[keyi])
left++;;
3.left--错误
int keyi = left;
left++；你想想，代码的后面是不是要交换的，可你现在left的位置是一直变化的，是不是就找不到原来的位置了啊？
所以呢？我们还要进行记录原来的位置下来：
int keyi = left;
int begin = left, end = right;最后，正确的代码应该是：
void QuickSort(int* a, int left,int right)
{
int keyi = left;
int begin = left, end = right;
while (left<right)
{
while (left<right &&a[right] >= a[keyi])
right--;
while (left<right &&a[left] <= a[keyi])
left++;;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
}接下来的部分，又两种的方法可以完成：一直是递归法，一种是非递归法。两种都要掌握。递归变非递归是每个程序员必备的技能，所以都需要会。
这里我们先来
快速排序的递归法：
大概递归的过程就是这样了。就是每次都分成两部分。
观察到，什么时候是结束递归？就是当left>=right时就返回来了。
它递归的范围是什么呢？第一趟完成的时候，我们可以很清楚看到，分成两部分的范围应该是：
[begin,keyi-1]keyi,[key+1,end]
有了上面的了解后，我们就可以写出来递归的代码了：直接对照范围写下来就可以了。
代码：
void QuickSort(int* a, int left,int right)
{
if (left>=right)
return;
int keyi = left;
int begin = left, end = right;
while (left<right)
{
while (left<right &&a[right] >= a[keyi])
right--;
while (left<right &&a[left] <= a[keyi])
left++;;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
//[0,keyi-1]keyi,[key+1,end]
QuickSort(a, begin, keyi-1);
QuickSort(a,keyi+1,end);
}其实，看下递归图后，不知道大家有没有一种熟悉感，就是它特别像二叉树？
而我们的二叉树中算过2^n-1的节点
所以若有N个数，每次它会减少一个数，所以排序的的平均时间复杂度大概是O(N*logN)；
但是它的最坏时为O(N^2);
完全逆序时，如上图，次数有等差数列直到，n^2/2 大概就是n^2了
证明：左边做key，右边先走，为啥相遇位置就是基准值的位置？
相遇：
1.R找到小的了，L没有找到大的，那么L会相遇R
2.R找小没有找到，直接遇到L，那么它就是比key基准值小的位置或者直接到到key基准值。
3.按照此类似的，当我们选取右边为基准值时，让左边先，也是同样的道理。
可是呢，当我们仅仅是取左边的数或者是右边的数，这偶然性太大了，万一它是最小的数/最大的数，这是不是效率就非常的低了。为了解决这种误差，大佬们想出了几种解决方法：
三数取中，取随机数，取完了之后再进行交换。这样就大大提高了它们的效率了。
三数取中：看名字知道，就是取三个数，比较大小，选取中间大的数做基准值。
三数取中：
//三数取中
int GetMidNum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if(a[left]>a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}取随机数：
//随机数
int randi = left+rand() % (right - left);
Swap(&a[randi], &a[left]);随便都可以用一个。
挖坑法：
动图：
代码：
void QuickSort2(int* a,int left,int right)
{
if (left >= right)
return;
//三数取中
//int midi = GetMidNum(a, left, right);
//if (midi != left)
//{
// Swap(&a[midi], &a[left]);
//}
int begin = left, end = right;
int key = a[left];
int hole = left;
while (left < right)
{
while (left<right &&a[right] >= key)
right--;
Swap(&a[right], &a[hole]);
hole = right;
while (left<right &&a[left] <= key)
left++;
Swap(&a[left], &a[hole]);
hole = left;
}
a[hole] = key;
//范围//[begin,empty-1][empty+1,end]
QuickSort2(a, begin, hole - 1);
QuickSort2(a, hole +1,end);
}
前后指针法：
动图：
步骤：
1.如果cur的值小于基准值，则prev++，且交换prev和cur的位置，cur++；
2.如果cur的值大于基准值，cur++；
3.看动图，我们知道当cur+1<n时，不进入循环，不能cur<n.
此时交换key的值和prerv的值
说明：
1.prev要么紧跟的cur（prev的next是cur）
2.prev跟cur中间间隔着比key基准值大的一段数的区间。
看到上面的红色部分，我们可以看出，prev和cur之间的区间是不是轮流翻转的规律的。
代码：
//指针法
void QuickSort3(int* a, int left, int right)
{
if (left >= right)
return;
int midi = GetMidNum(a, left, right);
if (midi != left)
{
Swap(&a[left], &a[midi]);
}
int keyi = left;
int prev = left, cur = left + 1;
while (cur < right+1)
{
if (a[cur] < a[keyi] && prev++ !=cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[keyi], &a[prev]);
//换了位置，keyi也要变，具体的选择排序那里有讲过原因
keyi = prev;
//
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}最后，到了本次的鸡汤部分：
我们都懂得努力，但不知道如何开始，既然还在边缘徘徊，何不如先扎根一回探其究竟，与其焦急等待，不如快速做出决定。当你再次回头的时候，也许你会看到同在起点的他们还在原地，而你已经超越。
