宝塔搭建本地网站,网站图片展示源代码,网页界面设计公司,美食推荐网站模板前言#xff1a;前面我们的排序已经详细的讲解了一系列的方法#xff0c;那么我们现在久之后一个归并排序了#xff0c;所以我们现在就来讲解一下归并排序。 归并排序#xff1a; 归并排序#xff08;MERGE-SORT#xff09;是建立在归并操作上的一种有效的排序算法,该算法… 前言前面我们的排序已经详细的讲解了一系列的方法那么我们现在久之后一个归并排序了所以我们现在就来讲解一下归并排序。 归并排序 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有 序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid][mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);// [begin, mid][mid1, end]归并int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}a是我们待排序的数组里面存放了要排序的数据tmp是我们额外开辟的数组用来存放我们排好序的数据而我们排好序的数据则是像链表一样尾插入数组的。我们先找出中间值给这个区间分成两个小区间两个小区间各自在分成小区间。从左到右逐一比较两个小区间中的元素把较小的元素优先放入额外开辟的数组tmp如果一个小区间的全部尾插到tmp中就结束了循环而另外一个数组则按顺序的尾插到tmp中。最后我们的tmp中的数据拷贝到数组a中就完成了。 void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}这里就是用来开辟额外数组tmp的我们传参到函数_MergeSort在_MergeSort中递归完成排序之后就返回再将开辟的空间销毁。 如果最大家有所帮助的话就支持一下吧感谢大家
