假设有一组数组
在其中任选一个基准值，假设是6
通过一些方法将序列分成左序列和右序列，左序列都小于基准值，右序列都大于基准值
只是将基准值的位置确定了，其它的数只是范围确定了，位置不一定对。
之后分别对左序列和右序列用同样的方式，让每个数在相应位置上。
接下来的介绍的方法，就是为了实现基准值在相应位置上。
假设对一个数组进行实现升序。 我们选定第一个数为基准值，在将基准值赋值给变量key后，将原来第一个数的位置看作一个坑，
并且在开头和最后位置建立变量begin、end，和建立变量pivot表示坑以便访问。第一步：左移动end，若end位置的值大于基准值（6），则end-1访问上一个位置，若end位置的值小于基准值（6），则将end位置的值放入pivot位置，而end位置就变成了pivot的位置。
第二步：移动begin，若begin位置的值小于基准值（6），则begin+1访问下一个位置，若begin位置的值大于基准值（6），则将begin位置的值放入pivot位置，而begin位置又变成了pivot的位置。
重复第一步和第二步，直到begin与end位置相等，再将基准值放入，这样就确定好了6的相应位置
值得注意的是，在pivot下标中是有值的，因为这个值是可以被覆盖，所以我们将其抽象为坑。
接下来对左右序列再次进行以上操作：
用递归代码实现：
//快排挖坑法
void QuickSort(int* a, int left, int right)
{
int begin = left, end = right;//begin,end需要改变的
//递归的限制条件，序列只剩一个或者序列为空返回。
if (begin >= end)
{
return;
}
int pivot = begin;
int tmp = a[pivot];
//实现一次让基准值在相应位置
while (begin < end)
{
//注意begin < end，当begin和end相等时停止
while (begin < end && a[end] >= tmp)
{
end--;
}
a[pivot] = a[end];
pivot = end;
while (begin < end && a[begin] <= tmp)
{
begin++;
}
a[pivot] = a[begin];
pivot = begin;
}
//再次将基准值定义为序列的第一个数
pivot = begin;
a[pivot] = tmp;
//访问左序列和右序列
//[left,pivot-1] pivot [pivot+1,right]
QuickSort(a, left, pivot - 1);
QuickSort(a, pivot + 1, right);
}
在单趟排序中，通过右边访问和左边下标访问，它们的次数总和就是N（数的数量），而在递归当中，结构呈现了一个树形结构，那么他的次数就是高度次，也就是logN，所以时间复杂度为O(N*logN)。
在让我们来看看，快排中什么情况下是最坏的。
答案是有序的情况下，让我们来看看具体
假设是1 2 3 4 … n
从这可见，确实基准值如果取到第一位是有问题的。
那么如何解决这个问题呢？
对于解决的方法，能够在有序的情况下，使得拆分的时候结构呈现较均匀树形结构，每次找到基准值后能够拆出左右两段，而不是有序时的每次一边的一大段。
三数取中这个方法就很好的解决了这个问题。
三数取中：从数组最开始位置、末尾位置和中间位置的三个数，挑第二大的值，并且和数组第一个值进行交换。
这样效率又能回到N*logN
用递归代码实现：
//三数取中
int GetMid(int* a, int left, int right)
{
int mid = (right + left) >> 1;
if (a[left] < a[mid])
{
if (a[left] > a[right])
{
return left;
}
else if (a[mid] < a[right])
{
return mid;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//快排挖坑法
void QuickSort(int* a, int left, int right)
{
int begin = left, end = right;//begin,end需要改变的
//递归的限制条件，序列只剩一个或者序列为空返回。
if (begin >= end)
{
return;
}
int mid = GetMid(a, left, right);//三数取中
Swap(&a[left], &a[mid]);
int pivot = begin;
int tmp = a[pivot];
//实现一次让基准值在相应位置
while (begin < end)
{
//注意begin < end，当begin和end相等时停止
while (begin < end && a[end] >= tmp)
{
end--;
}
a[pivot] = a[end];
pivot = end;
while (begin < end && a[begin] <= tmp)
{
begin++;
}
a[pivot] = a[begin];
pivot = begin;
}
//再次将基准值定义为序列的第一个数
pivot = begin;
a[pivot] = tmp;
//访问左序列和右序列
//[left,pivot-1] pivot [pivot+1,right]
QuickSort(a, left, pivot - 1);
QuickSort(a, pivot + 1, right);
}
2.2、快排的双指针法和hoare法
双指针法:
假设取一个基准值keyi（6），创建一个cur、一个prev指向如下位置。
每次对cur所在位置的值和keyi比较，如果比keyi小，先prev++，再交换prev和cur位置的值，交换后cur位置再++，直到cur越界停止，最后交换prev和keyi的值。
cur到达边界
之后再拆成左右两个区间，进行重复的方法。
//双指针快排
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int midi = GetMid(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
//先比较，如果小于了再进行++prev
if (a[cur] < a[keyi] &&
++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi=prev;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
hoare法：
还是假设取一个基准值keyi（6），创建left、right分别在如下位置。
如果right位置的值大于等于keyi，那么right–，直到遇到小于keyi的值停止，再通过left找到值大于keyi的，直到left和right坐标都分别找到了大于的值和小于的值，交换两个位置的值。
直到left==right，交换left位置和keyi位置的值。
这时又固定了基准值的位置，然后分别对左右两个区间进行重复的方法。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int midi = GetMid(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
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;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
2.3、快排的非递归实现
递归的最大缺点就是，当递归深度过深的时候，栈帧创建的太多会导致栈溢出（Stack overflow）。
所以当出现递归深度过高的时候，我们不得不考虑非递归。
而将递归代码改成非递归代码时，我们有：
- 用循环取代递归
- 用数据结构中的栈模拟递归过程
代码实现：
//快排的非递归实现
void QuickSortR(int* a, int n)
{
ST st;
StackInit(&st);
StackPush(&st, n-1);
StackPush(&st, 0);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int index = partion1(a, left, right);
//[left,index-1]index[index+1,right]
if (index + 1 < right)
{
StackPush(&st, right);
StackPush(&st, index + 1);
}
if (left < index - 1)
{
StackPush(&st, index - 1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}
3、归并排序的实现（包括递归与非递归）
假设以上的一个数组，先拆分到一个个，然后再2个数排序后合并，再4个数排序后合并，再8个数排序后合并，直到有序为止。
递归代码实现：
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
//如果空序列或者只有一个数的序列，返回
if (left >= right)
{
return;
}
//一直递归拆分，拆到序列剩两个数开始进行下面排序
int mid = (right + left) / 2;
//[left,mid] [mid+1,right]
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid+1, right, tmp);
//排序
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//把tmp中排序好的放入原来的地方
for (int j = left; j <= right; j++)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
//通过创建新的数组，
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc failn");
exit(-1);
}
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
归并和快排有一个很明显的区别，就是快排是先进行排序，再拆分，而归并是先拆分再排序的。
所以也使得归并的非递归似乎可以用循环来实现。
void _MergeSortR(int* a, int n, int* tmp)
{
int gap = 1;
while (gap < n)
{
for (int j = 0; j < n; j += gap * 2)
{
//[i,i+gap-1] [i+gap,i+2*gap-1]
//排序
int begin1 = j, end1 = j + gap - 1;
int begin2 = j + gap, end2 = j + 2 * gap - 1;
int i = j;
//右边序列不存在，直接跳出这个排序
if (begin2 >= n)
{
break;
}
//右边序列不全，end2直接赋值为最大位置
if (end2 >= n)
{
end2 = n - 1;
}
//排序
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//两个数排好序就直接赋值放回
for (int m = j; m <= end2; m++)
{
a[m] = tmp[m];
}
}
gap *= 2; //两两排好序后，四四排序以此类推
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc failn");
exit(-1);
}
_MergeSortR(a, n, tmp);
free(tmp);
tmp = NULL;
}
