上次我们讲解了快速排序的递归的几种做法。
那么，作为一名合格的程序员，改递归为非递归是必要的，现在我们来学习一下非递归的做法：
快速排序非递归：
首先，我们先了解一下，为什么要改为非递归？它有什么弊端？
1.递归有以下劣处：
1）效率问题（但是影响不是太大）对于排序。
2）递归太多会发生栈溢出。
我们举个例子来说明一下：
int Test(int n)
{
if (n <= 1)
return 1;
return n + Test(n);
}
int main()
{
printf("%d", Test(10000000));
return 0;
}
看，当 递归的深度太深的话，它就会出现上面的情况（栈溢出）。
那么，我们改怎么改成非递归呢？
这里我们利用到之前写过的栈来辅助完成
我们知道，栈是后进先出的规则
那么，我们以下面的数据来举例：
第一步：先入栈，两边的位置第一次也就是0和9的下标，这里要注意的是要先入右边right的下标，再入左边left的下标。
入完了之后，出数据（栈是只能栈顶出）
这样，我们就得到了这次使用的范围了，接着使用我们上章节讲过的快速排序的任意一种：取基准值，区分成两部分，一边比基准值小，一边比基准值大的那个过程的代码了，这里有写到。
这里为了方便，我直接封装成一个函数了，最后用返回值来记录每次基准值的下标位置。
int PartSort3(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 = prev;
return keyi;
}返回keyi基准值的下标位置后，如下图：
出栈时，我们记录下来当前栈顶的数据，分别为begin和end
那我们是不是有得到了一个范围了：[begin,keyi-1] keyi [keyi+1,end]
我们就继续来入栈（还是先入右边,看作整体）即： [keyi+1,right]
入完了之后再两个两个出
结束条件：left>keyi-1和 keyi+1>right
按照此过程循环就可以完成了。
void QuickSort4(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort3(a, begin, end);
//[begin,keyi-1]keyi[keyi+1,right]
if(keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi+1);
}
if(keyi - 1 > begin)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
Destory(&st);
}要注意：调用栈时，我们要注意栈的STTypeData的类型是否与此匹配。
归并排序
概念：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
它的动图：
我们根据动图知道，它需要一个临时的数组存数据。
所以先开辟临时数组吧：
void MergeSort(int* a,int n)
{
int* temp =(int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a,0,n-1, temp);
free(temp);
}步骤：
1.第一张图我们知道，它本来是一个数组的，然后每次将数组拆分成两部分。---拆解
这里我们就可以使用递归的方法，进行拆分，一步一步拆分，直到最后只剩下一下无法再拆分时，结束返回。
2.
这里，拆解的过程，我们看到，拆解成的两个数组是不是都得有开始和结尾。
所以，我们这里肯定不能只定义一个begin和end的，我们要定义begin1，begin2，end1，end2
那么，我们又怎么划分它们各自的范围呢？
我们看上图，发现分解的过程，是不是相当于一个面包分成两个，那我们是不是得找到数组的中间位置下标mid，有了mid后，看这图，我们可以写出他们的范围了
begin1=begin，end1=mid
begin2=mid+1，end2=end；
这里，我们比较数组的值大小，哪个小，就先存到临时数组里面去，以上图为例：
begin1与begin2比较，begin2小，先存到临时数组，然后begin2++，到9那个位置，继续比较，直到全部比完。
当某一个数组的数都完了，另一个数组就直接放到临时数组的后面了（因为单一的数组已经有序了）
当两个数组比完，排好序了，这是只是在临时数组里，我们还要再复制到原来的数组了。这里我们用memcopy这个函数来直接实现了。
下面给出之前写过的相关字符串的知识点，忘的话可以去复习复习。
代码：
void _MergeSort(int* a, int begin, int end,int* temp)
{
//结束条件
if (begin >= end)
return;
//中间数的下标
int mid = (begin + end) / 2;
//范围//[begin,mid][mid+1,end]
_MergeSort(a, begin, mid,temp);
_MergeSort(a, mid+1,end,temp);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
//printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
//printf("\n");
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
//比完，另一个数组还有值的情况
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//复制
memcpy(a+begin, temp+begin, sizeof(int) * (end - begin + 1));
}归并排序的非递归
我们可以看到，每次的变化是不是从1->2->4->8
呈两倍的增长速度，那么我们的递归改非递归，无非就是改成循环。
我们不妨来设置一个gap（间隔）来弄 成循环，每次二倍增长。如下
首先，我们内部的原理肯定是不变的，所以我们直接就以上面的为搬下来就可以了。
int begin1 , end1 ;
int begin2 end2 = ;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
//比完，另一个数组还有值的情况
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}那么好了之后，我们来写一下外部的循环，即呈两倍增长的过程
int gap=1;
for (int i = 0; i < n; i += 2 * gap)
{
//单趟
int begin1=i, end1=i+gap-1;
int begin2=gap+i, end2=i+2*gap-1;
int j = i;
…………
…………
…………
}注意：这里i初始化的值不同，会导致下面begin1，end1，begin2，end2也不同，可以按照自己不同的情况来定begin1，end1，begin2，end2。
这里我采用的是i=0时，我们可以代进去数据来看。
i=0时，begin1=0，end1=0+1-1=0；
begin2=1+0=1，end2=0+2*1-1=1
这是不是就符合我们上面所说的分组的位置逻辑了。
什么时候结束？当gap的增长超过n长度时
int gap=1;
while(gap<n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//单趟
int begin1=i, end1=i+gap-1;
int begin2=gap+i, end2=i+2*gap-1;
int j = i;
…………
…………
…………
}
gap*=2;
}坑：
这里有一个很容易掉坑的细节：memcpy放的位置，是放在for循环里面，还是外面呢？
那么，这又有什么区别呢？
放在for循环里面：归并一部分拷贝一部分
放在for循环外面：间距为gap的多组数据，归并完之后，再一下子拷贝下来。
memcpy(a, temp, sizeof(int) * (end2-i+1));现在，我们先来讲放在for循环外面的情况先：
我们按照这种运行后，会发现程序崩了
这里有一种非常实用的技巧：
调试技巧:
就是打印出来他们的下标
printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);void _MergeSortNon(int* a, int n, int* temp)
{
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//单趟
int begin1=i, end1=i+gap-1;
int begin2=gap+i, end2=i+2*gap-1;
int j = i;
观察---------------------------------------------------
printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
-------------------------------------------------------
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[j++] = a[begin1++];
}
else
{
temp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = a[begin2++];
}
}
memcpy(a, temp, sizeof(int) * (end2-i+1));
gap *= 2;
//printf("\n");
}
}观察后，我们得到下图： 发现9个数，那么它的下标范围就是0-8，可是我们打印出来的却有9以上的，说明这问题就出现在越界的情况。
现在我们来分析分析：讲复杂问题简单化：分类处理：
1.end1越界了，我们该怎么办？就不归并了。因为ta
2.end1没有越界，但begin2越界了，该怎么办？就不归并了。
3.end2越界了，该怎么办？继续归并，修改end2.
现在，你是把memcpy放到外面，归并完之后，再一下子拷贝下来的。
我们来修正路线：
很多人认为，应该这样子修正：
if (end1 >= n)
{
end1=n-1;
begin2=n-1;
end2 = n - 1;
} 可是，
这不就成了这样子了吗？而你是一下拷贝下来的
相当于，你把这蓝色部分也算上了，你memcpy时，临时数组的蓝色位置是随机值，如果你直接拷贝的话，你会把原来数组蓝色部分的地方覆盖了，也会变成随机值。也会发生错误。
所以，我们正确的应该是：
if (end1 >= n)
{
end1=n-1;
begin2=n;
end2 = n - 1;
}
else if (begin2 >= n)
{
begin2=n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
这样begin2-end2的范围：[n,n-1],不符合条件，进不去。
看到了放到外面的繁杂了吧，所以一般说，我们不会采用这种，通常是放到for循环里面，一部分一部分拷贝，更可靠。
放到里面：
这样，我们修改路线：
if (end1 >= n && begin2>=n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
因为，我们是一部分一部分拷贝的，所以我们 遇到第一种情况，就break就行了，不用担心它会不会覆盖情况。
完整代码：
void _MergeSortNon(int* a, int n, int* temp)
{
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//单趟
int begin1=i, end1=i+gap-1;
int begin2=gap+i, end2=i+2*gap-1;
int j = i;
if (end1 > n || begin2>n)
{
break;
}
if (end2 > n)
{
end2 = n - 1;
}
//printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[j++] = a[begin1++];
}
else
{
temp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = a[begin2++];
}
memcpy(a, temp, sizeof(int) * (end2-i+1));
}
gap *= 2;
//printf("\n");
}
}
void MergeSortNon(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
return;
}
_MergeSortNon(a, n,temp);
free(temp);
}