企业官网建设流程全解析

微信分享的h5网站开发,深圳医疗网站建设公司,微商城手机网站,建设跨境网站1、快速排序#xff08;非递归#xff09; 思路 这里实现的是深度优先遍历#xff08;DFS#xff09;#xff0c;我们使用栈来模拟实现 *所以我们利用栈的先进后出的特点#xff0c;在模拟实现递归的时候先将右边的压栈#xff0c;再将左边的压栈 每访问完一个数据就按照…1、快速排序非递归思路这里实现的是深度优先遍历DFS我们使用栈来模拟实现*所以我们利用栈的先进后出的特点在模拟实现递归的时候先将右边的压栈再将左边的压栈每访问完一个数据就按照这个顺序将它的左右两边的栈压进去然后访问栈顶实现//这里应该加一个指向栈的链接voidQuickSortNoRec(int*arr,intleft,intright){//先将右边的数据存进去读的时候就可先读左边的了stack st1;st1.StackPush(right);st1.StackPush(left);while(!st1.Isempty()){//读取左右区间intbeginst1.StackPop();intendst1.StackPop();//进行排序intkeyQuickPart1(arr,begin,end);//先将右边的数据存进去if(key1end){st1.StackPush(end);st1.StackPush(key1);}if(beginkey-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(leftright)return;//这里我们为啥不先写一个判断条件来判断这个数组是不是有序的呢//因为我们在归并的时候无非就是将整个数组分为两半再遍历一遍我们这里就没必要脱裤子放屁了intmid(leftright)/2;_MergeSort_(arr,temp,left,mid);_MergeSort_(arr,temp,mid1,right);intbegin1left,end1mid;intbegin2mid1,end2right;inti0;while(begin1end1begin2end2){if(arr[begin1]arr[begin2])temp[i]arr[begin1];elsetemp[i]arr[begin2];}while(begin1end1){temp[i]arr[begin1];}while(begin2end2){temp[i]arr[begin2];}memcpy((arrleft),temp,(right-left1)*sizeof(int));}voidMergeSort(int*arr,intn){//我们这里在原数组里直接malloc数组但是我们不直接使用这个函数递归//因为我们如果直接使用原数组递归的话将会malloc很多次这是很浪费的int*temp(int*)malloc(sizeof(int)*n);_MergeSort_(arr,temp,0,n-1);free(temp);}时间复杂度ON*logN每一层遍历一遍是遍历了N个相当于是遍历了logN层空间复杂度O(N)创建了N个大小的新空间temp数组void_MergeSort_(int*arr,int*temp,intleft,intright){if(leftright)return;//这里我们为啥不先写一个判断条件来判断这个数组是不是有序的呢//因为我们在归并的时候无非就是将整个数组分为两半再遍历一遍我们这里就没必要脱裤子放屁了intmid(leftright)/2;_MergeSort_(arr,temp,left,mid);_MergeSort_(arr,temp,mid1,right);intbegin1left,end1mid;intbegin2mid1,end2right;intileft;while(begin1end1begin2end2){if(arr[begin1]arr[begin2])temp[i]arr[begin1];elsetemp[i]arr[begin2];}while(begin1end1){temp[i]arr[begin1];}while(begin2end2){temp[i]arr[begin2];}memcpy((arrleft),(templeft),(right-left1)*sizeof(int));}这是修改版修改了i的起始位置从left开始依次将数据填入temp最后从arrleft的位置将数据拷贝回去易踩的坑![[Pasted image 20251223201214.png]]我们在计算中间值的时候如果直接/2就会丢失数据1所以在相邻的偶数和偶数加一的情境下会出现死循环![[Pasted image 20251223201657.png]]这是就可以了这里实际上是巧妙的避开了3、归并排序非递归思路使用的是循环思路是将递归的思路反过来一次对两组数据进行排序一次排两组![[Pasted image 20251223213049.png]]intgap1;for(inti0;in;i2*gap){intbegin1i,end1igap-1;intbegin2igap,end2i2*gap-1;//......}这里的外层for循环是用来找每一次排序的头指针的这里的gap就是每一组的数据个数这里又出bug了在这里[[2025 12 23 bug]]这是可以对2的次方倍进行排序的版本voidMergeSortNoRec(int*arr,intn){int*temp(int*)malloc(sizeof(int)*n);if(nullptrtemp){perror(malloc fail);return;}intgap1;while(gapn){for(inti0;in;i2*gap)//气笑了少加了个等于号{//这是个大坑忘记做备份了intji;intbegin1j,end1jgap-1;intbegin2jgap,end2j2*gap-1;printf([%d,%d] [%d,%d] ,begin1,end1,begin2,end2);while(begin1end1begin2end2){if(arr[begin1]arr[begin2])temp[j]arr[begin1];elsetemp[j]arr[begin2];}while(begin1end1){temp[j]arr[begin1];}while(begin2end2){temp[j]arr[begin2];}memcpy((arri),(tempi),(end2-i1)*sizeof(int));}gap*2;printf(\n);}}这个程序还是有问题的我们来改一下这里并没有对2的n次以外的数据做出考量是会越界的![[Pasted image 20251223223119.png]]我们在第一次排的数据肯定是没问题的这里就可以看出我们从第二次开始就开始越界了![[Pasted image 20251223215713.png]]分析得出后两种情况在这个循环中就不用归并了直接跳到下一个因为此时前面的已经归并过了第一种情况还是要归并的但是要将end2改为n-1(这里的n是闭区间)if(begin2n)break;if(end2n)end2n-1;最终代码voidMergeSortNoRec(int*arr,intn){int*temp(int*)malloc(sizeof(int)*n);if(nullptrtemp){perror(malloc fail);return;}intgap1;while(gapn){for(inti0;in;i2*gap)//气笑了少加了个等于号{//这是个大坑忘记做备份了intji;intbegin1j,end1jgap-1;intbegin2jgap,end2j2*gap-1;if(begin2n)break;if(end2n)end2n-1;printf([%d,%d] [%d,%d] ,begin1,end1,begin2,end2);while(begin1end1begin2end2){if(arr[begin1]arr[begin2])temp[j]arr[begin1];elsetemp[j]arr[begin2];}while(begin1end1){temp[j]arr[begin1];}while(begin2end2){temp[j]arr[begin2];}memcpy((arri),(tempi),(end2-i1)*sizeof(int));}gap*2;printf(\n);}}