只做健康产品的网站,网络营销十大成功案例,网站服务器做缓存,网站配色原理制作不易#xff0c;三连支持一下吧#xff01;#xff01;#xff01; 文章目录 前言一.归并排序递归方法实现二.归并排序非递归方法实现 前言
这篇博客我们将介绍归并排序的原理和实现过程。 一、归并排序递归方法实现 基本思想#xff1a; 归并排序#xff08;MERGE-… 制作不易三连支持一下吧 文章目录 前言一.归并排序递归方法实现二.归并排序非递归方法实现 前言
这篇博客我们将介绍归并排序的原理和实现过程。 一、归并排序递归方法实现 基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 1.分解 将所给序列一分为二直到区间中只有一个元素时停止。这个过程是递归进行的通过传递区间参数来控制。 2. 合并 相邻两个子数组有序之后就递归合并这两个子数组将它们合并成一个新的有序子数组。 动图演示如下 归并时我们是借助一个临时数组tmp来合并两个有序子数组。 代码实现如下
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid 1, end, tmp);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));
}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(n * sizeof(int));_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp NULL;
} 二、归并排序非递归方法实现
同快速排序一样如果递归深度过深可能会导致栈溢出这样的情况下我们就不能用递归法来实现归并排序。 上篇博客提到将递归改成非递归的一般方法有两种 一种是直接改循环如斐波那契数列。 另一种是借助栈或队列例如快速排序。 这里我们借助栈也无法完成归并排序因此我们只能选择循环。
代码实现如下
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc:);return;}int gap 1;while (gap n){for (int j 0; j n; j 2*gap){int begin1 j, end1 begin1 gap - 1;int begin2 end1 1, end2 begin2 gap - 1;int i j;if (end1 n || begin2 n){break;}//处理数组越界的情况if (end2 n)end2 n - 1;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 j, tmp j, sizeof(int) * (end2 - j 1));}gap * 2;}free(tmp);tmp NULL;
}
