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);}| 时间复杂度 | O（N*logN） | 每一层遍历一遍是遍历了N个，相当于是遍历了logN层 |
|---|---|---|
| 空间复杂度 | O(N) | 创建了N个大小的新空间（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");}}
