一个人做网站可以做什么,wordpress特定页面设为主页,用手机如何做网站,网站开发的人怎么样归并排序#xff1a;#xff08;MERGE-SORT#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法#xff08;Divide and Conquer#xff09;的一个非常典型的应用。将已有序的子序列合并#xff0c;得到完全有序的序列#xff1b;即先使每个子序列有序…归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 也就是假设左边有序右边有序然后合并在一起归并后就有序。归并要借助临时的第三方数组。 不一定是均分只是下面的例子正好比较均匀。 快排是前序归并是后续。 归并是先递归到两个数再归并一层一层往回返着归并排序。 时间复杂度O(N*logN) 空间复杂度O(N) — 开辟临时数组 // 归并排序递归实现
void _MergeSort(int* a, int left, int right, int* tmp)
{//分到最后区间只有一个数或者没有这样的区间了返回。if(left right){return;}int mid (left right)/2;//[left, mid] [mid1, right]_MerageSort(a, left, mid, tmp);_MerageSort(a, mid1, right, tmp);// 两段有序子区间归并放到tmp中然后拷贝回aint begin1 left, end1 mid;int begin2 mid1, end2 right;int i left;// 在两个区间中选择小的数先放进tmpwhile(begin1 end1 begin2 end2){if(a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//将两个区间中没放完的那个区间的有序数组尾插到tmp中while(begin1 end1)tmp[i] a[begin1];while(begin2 end2)tmp[i] a[begin2];// 将tmp的数据返回给a right是下标 所以得for(int j left; jright; j)a[j] tmp[j];
}
void MergeSort(int* a, int n) //n传参传的是数组的大小
{int* tmp (int*)malloc(sizeof(int)*n)_MergeSort(a, 0, n-1, tmp) //n-1传参传的是数组下标的闭区间大小free(tmp);
}非递归方法每次归完后都需要将归好的数组返回给原数组。最后将有序的tmp给a然后释放tmp。 代码控制中有个gapgap是1 就是11归(两个相比)gap是2就是22归(四个相比) gap是4就是44归(八个相比)。 问题 1.最后一个小组归并时第一个小区间不够gap个则不需要归并 不处理时OK的 因为他同样满足第二个小区间不存在因此不处理OK。 2.最后一个小组归并时第二个小区间不存在则不需要归并了 3.最后一个小组归并时第二个小区间存在但是第二个区间不够gap个 问题1和问题2可以合并处理。 // 归并排序非递归实现
void _Merge(int*a, int* tmp, int begin1, int end1, int begin2, int end2)
{int i begin1;int j begin1;// 在两个区间中选择小的数先放进tmpwhile(begin1 end1 begin2 end2){if(a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//将两个区间中没放完的那个区间的有序数组尾插到tmp中while(begin1 end1)tmp[i] a[begin1];while(begin2 end2)tmp[i] a[begin2];// 将tmp的数据返回给a right是下标 所以得for(; jend2; j)a[j] tmp[j];
}
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n)_MergeSort(a, 0, n-1, tmp) //n-1传参传的是数组下标的闭区间大小int gap 1;while(gap n){//进来gap 1是11 gap 2 是22 gap4 是44for(int i0; in; i 2*gap){int begin1 i, end1 igap-1, begin2 igap, end2 i2*gap-1;//第二个小区间不存在则不需要归并了if(begin2 n)break;//第二个区间存在但是第二个区间不够gap个结束位置越界了需要修正if(end2 n)end2 n-1;//循环控制归并的边界啊// [i, igap-1] [igap, i2*gap-1] ..._Merge(a, tmp, begin1 , end1 , begin2, end2); //传的就是两个边界 每次传两个边界}gap * 2;} free(tmp);
}计数统计排序计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1.统计相同元素出现次数 2.根据统计的结果将序列回收到原来的序列中 时间复杂度O(max(N,rang)) 就是N和范围谁大就是O谁。 适合一组数据数据范围比较集中优秀的排序。 空间复杂度O(range) 范围集中效率高具有局限性。并且只适合整数。 // 计数排序
void CountSort(int* a, int n)
{int max a[0], min a[0];for(int i 0; i n; i){if(a[i] max)max a[i];if(a[i] min)min a[i];}int range max-min 1;int* count (int*)malloc(sizeof(int)*range);memset(count, 0, sizeof(int)*range); //将count初始化为0for(int i 0; in; i){count[a[i] - min] //让对应的位置}//写入a中int i0;for(int j0; jrange; j) // 循环count数组{while(count[j]--)//让这个位置的次数一直-到0 就打印完了次数。{a[i] jmin;}}free(count);
}
