快排（非递归）和归并的实现

1、快速排序（非递归）

思路

这里实现的是深度优先遍历（DFS），我们使用栈来模拟实现

*所以我们利用栈的先进后出的特点，在模拟实现递归的时候先将右边的压栈，再将左边的压栈

每访问完一个数据就按照这个顺序将它的左右两边的栈压进去，然后访问栈顶

实现

//这里应该加一个指向栈的链接

voidQuickSortNoRec(int*arr,intleft,intright){//先将右边的数据存进去，读的时候就可先读左边的了stack st1;st1.StackPush(right);st1.StackPush(left);while(!st1.Isempty()){//读取左右区间intbegin=st1.StackPop();intend=st1.StackPop();//进行排序intkey=QuickPart1(arr,begin,end);//先将右边的数据存进去if(key+1<end){st1.StackPush(end);st1.StackPush(key+1);}if(begin<key-1){st1.StackPush(key-1);st1.StackPush(begin);}}}

我这里写的栈是不标准的，我将Pop和Top和到一起了

2、归并排序（递归）

思路

***归并排序很像我们之前做的那个将两个有序数组合成一个有序数组

他就像是每一次进入函数后先判断是不是有序的，然后多次分割，知道小块有序，才开始往回返，对父数组进行排序

***实际上像是一个后序遍历

![[Pasted image 20251223194437.png]]

![[归并排序.gif]]

实现

void_MergeSort_(int*arr,int*temp,intleft,intright){if(left==right)return;//这里我们为啥不先写一个判断条件来判断这个数组是不是有序的呢//因为我们在归并的时候无非就是将整个数组分为两半，再遍历一遍，我们这里就没必要脱裤子放屁了intmid=(left+right)/2;_MergeSort_(arr,temp,left,mid);_MergeSort_(arr,temp,mid+1,right);intbegin1=left,end1=mid;intbegin2=mid+1,end2=right;inti=0;while(begin1<=end1&&begin2<=end2){if(arr[begin1]<arr[begin2])temp[i++]=arr[begin1++];elsetemp[i++]=arr[begin2++];}while(begin1<=end1){temp[i++]=arr[begin1++];}while(begin2<=end2){temp[i++]=arr[begin2++];}memcpy((arr+left),temp,(right-left+1)*sizeof(int));}voidMergeSort(int*arr,intn){//我们这里在原数组里直接malloc数组，但是我们不直接使用这个函数递归//因为我们如果直接使用原数组递归的话，将会malloc很多次，这是很浪费的int*temp=(int*)malloc(sizeof(int)*n);_MergeSort_(arr,temp,0,n-1);free(temp);}

void_MergeSort_(int*arr,int*temp,intleft,intright){if(left==right)return;//这里我们为啥不先写一个判断条件来判断这个数组是不是有序的呢//因为我们在归并的时候无非就是将整个数组分为两半，再遍历一遍，我们这里就没必要脱裤子放屁了intmid=(left+right)/2;_MergeSort_(arr,temp,left,mid);_MergeSort_(arr,temp,mid+1,right);intbegin1=left,end1=mid;intbegin2=mid+1,end2=right;inti=left;while(begin1<=end1&&begin2<=end2){if(arr[begin1]<arr[begin2])temp[i++]=arr[begin1++];elsetemp[i++]=arr[begin2++];}while(begin1<=end1){temp[i++]=arr[begin1++];}while(begin2<=end2){temp[i++]=arr[begin2++];}memcpy((arr+left),(temp+left),(right-left+1)*sizeof(int));}

这是修改版，修改了i的起始位置，从left开始依次将数据填入temp，最后从arr+left的位置将数据拷贝回去

易踩的坑

![[Pasted image 20251223201214.png]]
我们在计算中间值的时候如果直接/2就会丢失数据（1），所以在相邻的偶数和偶数加一的情境下会出现死循环
![[Pasted image 20251223201657.png]]
这是就可以了

这里实际上是巧妙的避开了

3、归并排序（非递归）

思路

使用的是循环，思路是将递归的思路反过来，一次对两组数据进行排序

一次排两组
![[Pasted image 20251223213049.png]]

intgap=1;for(inti=0;i<n;i+=2*gap){intbegin1=i,end1=i+gap-1;intbegin2=i+gap,end2=i+2*gap-1;//......}

这里的外层for循环是用来找每一次排序的头指针的

这里的gap就是每一组的数据个数

这里又出bug了
在这里[[2025 12 23 bug]]

这是可以对2的次方倍进行排序的版本

voidMergeSortNoRec(int*arr,intn){int*temp=(int*)malloc(sizeof(int)*n);if(nullptr==temp){perror("malloc fail");return;}intgap=1;while(gap<n){for(inti=0;i<n;i+=2*gap)//气笑了，少加了个等于号{//这是个大坑，忘记做备份了intj=i;intbegin1=j,end1=j+gap-1;intbegin2=j+gap,end2=j+2*gap-1;printf("[%d,%d] [%d,%d] ",begin1,end1,begin2,end2);while(begin1<=end1&&begin2<=end2){if(arr[begin1]<arr[begin2])temp[j++]=arr[begin1++];elsetemp[j++]=arr[begin2++];}while(begin1<=end1){temp[j++]=arr[begin1++];}while(begin2<=end2){temp[j++]=arr[begin2++];}memcpy((arr+i),(temp+i),(end2-i+1)*sizeof(int));}gap*=2;printf("\n");}}

这个程序还是有问题的，我们来改一下

这里并没有对2的n次以外的数据做出考量，是会越界的

![[Pasted image 20251223223119.png]]
我们在第一次排的数据肯定是没问题的

这里就可以看出我们从第二次开始就开始越界了

![[Pasted image 20251223215713.png]]

分析得出：

后两种情况在这个循环中就不用归并了，直接跳到下一个（因为此时前面的已经归并过了）

第一种情况还是要归并的，但是要将end2改为n-1(这里的n是闭区间)

if(begin2>=n)break;if(end2>=n)end2=n-1;

最终代码

voidMergeSortNoRec(int*arr,intn){int*temp=(int*)malloc(sizeof(int)*n);if(nullptr==temp){perror("malloc fail");return;}intgap=1;while(gap<n){for(inti=0;i<n;i+=2*gap)//气笑了，少加了个等于号{//这是个大坑，忘记做备份了intj=i;intbegin1=j,end1=j+gap-1;intbegin2=j+gap,end2=j+2*gap-1;if(begin2>=n)break;if(end2>=n)end2=n-1;printf("[%d,%d] [%d,%d] ",begin1,end1,begin2,end2);while(begin1<=end1&&begin2<=end2){if(arr[begin1]<arr[begin2])temp[j++]=arr[begin1++];elsetemp[j++]=arr[begin2++];}while(begin1<=end1){temp[j++]=arr[begin1++];}while(begin2<=end2){temp[j++]=arr[begin2++];}memcpy((arr+i),(temp+i),(end2-i+1)*sizeof(int));}gap*=2;printf("\n");}}