vuejs 做网站 性能,招聘网站做精准 置顶,用旧手机做网站,视频网站怎么做网站引流之前我们学习过把两个有序数组合并再一起后任然有序#xff0c;就叫归并#xff1b; 那么#xff0c;排序是否也可以把一个要排序的数组分割成两个有序的数组#xff0c;然后归并#xff0c;之后再拷贝回原数组#xff0c;就实现了排序 但是怎么才能控制分割成的数组是有…之前我们学习过把两个有序数组合并再一起后任然有序就叫归并 那么排序是否也可以把一个要排序的数组分割成两个有序的数组然后归并之后再拷贝回原数组就实现了排序 但是怎么才能控制分割成的数组是有序的呢 当 当数组中只有两个数的时候我们进行分割后每一个数组就只有一个数就可以看成有序的
有了这个思想那么我们就递归分个要排序的数组当递归分割到只有两个数的时候在归并
void Merge(int* a, int* tmp, int begin, int end)
{//分割if (begin end){return;}int mid (begin end) / 2;Merge(a, tmp, begin, mid);Merge(a, tmp, mid 1, end);//归并int begin1 begin;int end1 mid;int begin2 mid 1;int end2 end;int dex begin;while (begin1end1begin2end2){if (a[begin1] a[begin2]){tmp[dex] a[begin1];dex;begin1;}else{tmp[dex] a[begin2];dex;begin2;}}while (begin1 end1){tmp[dex] a[begin1];dex;begin1;}while (begin2 end2){tmp[dex] a[begin2];dex;begin2;}//拷贝回去memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);Merge(a,tmp,0,n-1);
}非递归的写法 之前的快速排序是借助栈来实现非递归因为每次分完之后他就找出了key的位置那个区间出栈后不需要再用到 但是归并排序的话分割完后还要用到之前的分割区间但是都已经出栈了就找不到了。所以归并排序的非递归不能用栈来实现 但是这样的归并方式只适合数组中的元素个数是2的指数倍如果我们要适合其他区任何个数的话在划分区间归并的时候还的判断是否越界 代码
void MergeSortNoNs(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);int pas 1;while (pasn){for (int i 0; i n; i pas * 2){int begin1 i; int end1 i pas - 1;int begin2 i pas; int end2 i 2 * pas - 1;//越界管理if (begin2 n){break;}if (end2 n){end2 n - 1;}int dex i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[dex] a[begin1];dex;begin1;}else{tmp[dex] a[begin2];dex;begin2;}}while (begin1 end1){tmp[dex] a[begin1];dex;begin1;}while (begin2 end2){tmp[dex] a[begin2];dex;begin2;}//拷贝回去memcpy(a i, tmpi, (end2-i1) * sizeof(int));}pas * 2;}
}
