企业官网建设流程全解析

镇江网站建设多少钱,个人网页制作模板教程,临安网站建设公司,潍坊网站制作推广在学习归并排序之前#xff0c;个人认为需要掌握双指针的相关知识#xff08;快慢指针#xff0c;左右指针之类的#xff09;。归并排序是一种运用快慢指针与递归来实现的算法思路拆分过程-“归”的过程对于数组#xff1a;5 4 3 2 1我们先把…在学习归并排序之前个人认为需要掌握双指针的相关知识快慢指针左右指针之类的。归并排序是一种运用快慢指针与递归来实现的算法思路拆分过程-“归”的过程对于数组5 4 3 2 1我们先把其分为两部分5 4 和 3 2 1 //两个都可以看你选择5 4 3 和 2 1 //两个都可以看你选择然后再对于左右两部分再次拆分直到分成一个元素而这个过程我们可以运用递归来进行数组的拆分f(0 , 4)-f(0 , 2) f(3 , 4)-f(0 , 1) f(2 , 2) f(3 , 3) f(4, 4) //返回的是边界下标而我们就可以利用这个过程将大数组转换成小数组最终得到一个有序的数组排序过程-“并”的过程我们取递归返回的其中一个过程为例3 4 5 和 1 2我们定义一个临时变量来存储部分排序好的元素假设这个变量为temp我们先比较 3 和 1发现 1 比较小于是我们把 1 放入temp继续比较 3 和 2 发现 2 比较小于是我们把 2 放入temp这个时候右数组到头了于是我们停止比较并且把左数组剩下的元素全放到temp里面去于是我们得到的temp就是1 2 3 4 5然后我们将temp赋值给原数组把原数组覆盖掉我们明显可以发现和原来相比较原数组更加有序了已经有序了我们取的是排序的最后一步代码实现#includeiostream using namespace std; const int N 1e5; int arr[N]; int temp[N]; //辅助数组 void merge_sort(int l , int r){ //递归实现归并排序 if(l r) return; //只有一个元素或者没有自然有序不用管 int m (l r) / 2; //这里就是把数组拆开 merge_sort(l , m); //处理左边 merge_sort(m 1 , r); //处理右边 int i l , j m 1 , k 0; //i和j分别代表左右数组的左边界起点 k是临时变量作为temp数组的边界 while(i m j r){ if(arr[i] arr[j]){ temp[k] arr[j]; //把小的数放进来 k; j; }else{ temp[k] arr[i]; } } //接下来判断i和j哪个没走完把剩下的元素放进去 while(i m) temp[k] arr[i]; while(j r) temp[k] arr[j]; //然后把temp覆盖arr即把temp重新赋值给arr,arr的起始位置是l和rtemp的起始位置是0 for(i l , k 0 ; i r ; i , k){ arr[i] temp[k]; } } int main(){ int n; cin n; for(int i 0 ; i n ; i){ cin arr[i]; } merge_sort(0 , n - 1); //将左边界和右边界传入 for(int i 0 ; i n ; i){ cout arr[i] ; } cout endl; return 0; }总结归并排序的整体难度起始不大然后复杂度和稳定性这两个方面的话我不清楚这个复杂度是怎么算出来的但是我查出来是O()。归并排序不是一个稳定的算法因为临时数组会反复地把原数组进行覆盖。