企业手机网站建设策划书,西安关键词优化软件,专业医疗网站建设,专业企业网站搭建推荐文章目录一、归并排序#xff08;递归版#xff09;二、归并排序#xff08;非递归版#xff09;一、归并排序#xff08;递归版#xff09; 归并排序思想#xff1a;将数组划分为两个区间#xff0c;左区间#xff0c;右区间 然后对这两个区间内容进行排序 #xff…
文章目录一、归并排序递归版二、归并排序非递归版一、归并排序递归版 归并排序思想将数组划分为两个区间左区间右区间 然后对这两个区间内容进行排序 这两个区间排好序之后再将其合并为一个有序的区间 这两个区间排好序之后再将这两个区间合并为一个区间 也就是将这两个区间的数据排序为一个有序的区间 而将数组划分为两个区间之后是如何将这两个区间里的内容排好序的呢 是重复同样的操 作再将这两个区间中的左区间分别又划分为两个区间左区间右区间 将这两个区间分别排好序之后 再归为一个区间也就是左区间有序了然后再排它的右区间此时它的右区间右划分为两个区间左区间右区间 对它们分别进行排序 而划分下去的左右区间又要执行同样的操作直到最后区间大小为一时那么此时就不用排返回返回时与另一个区间比较进行排序 最后右区间变为有序的了最后将这两个大的左右区间归并排序为一个区间此时这个区间有序 由于递归排序回来时将小区间排好序最后整个大区间跟着有序了 我上图只是画了整个数组左区间的右区间可以下去尝试下右区间也是如此 void _MergeSort(int* a, int left, int right, int* tmp)
{//当区间中只有一个数时就不用再对其进行排序if (left right)return;//每次将其区间折半划分为左区间和右区间int mid (left right) / 2;//再重复划分直到它的左右区间只剩下一个数那么再返回//对其排序_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);//将其小区间排好序后再排它的大区间//小区间有序之后大区间排过来也就是有序的了int begin1 left, end1 mid;int begin2 mid 1, end2 right;int begin left;//将左右区间合并为一个区间while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[begin] a[begin2];}else{tmp[begin] a[begin1];}}//两个区间中还剩余数据的那个区间直接尾插到tmp数组后面while (begin1 end1){tmp[begin] a[begin1];}while (begin2 end2){tmp[begin] a[begin2];}//最后将排好序的区间拷贝回原来的数组memcpy(a left, tmpleft, sizeof(int)*(right - left 1));
}void MergeSort(int* a, int n)
{//开一个临时数组用来存放小区间排序后的数据//最后再将排序后的数组拷贝回原数组中int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);return;}//归并排序分两区间进行_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
二、归并排序非递归版 思想将整个数组一个数与一个数比较然后将它们排序为一个有两个数的区间 得到两个数与两个数之间有序 再将有两个数的区间与另外有两个数的区间进行排序为一个有四个数的区间 得到四个数的区间与四个数的区间有序 再将四个数的有序区间与四个数的有序区间进行排序为一个有8个数的有序区间 得到8个数与8个数之间有序 如此循环下去直到区间中数据的个数为原数组数据个数时为止 那么区间中的数据个数如何控制它又是如何变化的设定一个变量gap来控制然后当数组里面的数据都两两归并后gap变为原来2倍 gap * 2 当数组长度不是gap倍数时要注意控制边界。
那这个边界如何控制 设前一个区间左端begin1,右端end1 设后一个区间左端为:begin2,右端end2 如果第一个区间的右端已经超出了数组长度(end1n)此时将第一个区间右端下标重定为数组长度-1(end1 n-1, begin2 n, end2 n-1)如果前一个区间右端没有超出但是第二个区间左端就超出了重定begin2 n-1,end2 n-1,这样后一个区间就不用再与前一个区间合并了直接将前一个区间拷到原数组后面如果后一个区间左端没有超出但是后一个区间右端超出了数组长度此时重定end2,end2 n-1,此时前一个再与后一个合并 ** 将tmp中内容拷贝回原数组**
将间隔为gap的小区间归并后的内容整体拷贝回原数组
void MergeSort1(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);return;}int gap 1;while (gap n){//小区间由gap控制且每次都是前一个区间和后一个区间//归并为一个大的有序区间所以每次i需要加上gap的2倍//一次跳过两个区间for (int i 0; i n; i 2*gap){//控制区间范围数据个数int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap-1;int j i;//由于两个小区间要合并为一个区间//然后存放到数组tmp中合并后数组tmp长度大小//为两个小区间长度大小之和然后下次在开始合并时//从合并后的右端下标开始赋值所以tmp下标起始由i//决定if (end1 n){end1 n - 1;begin2 n ;end2 n-1;}else if (begin2 n){begin2 n ;end2 n-1;}else if(end2 n ){end2 n - 1;}//两个区间中小的数尾插到tmp数组中while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}}//将间隔为gap小区间合并后的数组tmp里的内容全部拷贝回原数组中memcpy(a, tmp, sizeof(int) * n);gap * 2;//最后gap变为原来的2倍}free(tmp);
}将间隔为gap的小区间一段一段的拷贝回原数组
void MergeSort2(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail\n);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int j i;//由于gap使其分区间块化有序此时前一个区间的右端//或者后一个区间的左端超出数组长度了那么直接//拷贝到原数组后面if (end1 n || begin1 n){break;}else if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//每一次区间间隔为gap的两个区间合并后就将其拷贝到//原数组中memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
} 归并排序将两个有序的区间归并为一个有序的区间
