本文共 3419 字,大约阅读时间需要 11 分钟。
当一个算法在结构上是递归的:即算法一次或多次调用自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后在合并这些子问题的解来建立原问题的解。
分治法在每层递归上都有三个步骤:
归并排序算法完全遵循分治模式,直观上的操作为:
合并:合并两个已经排序的子序列以 产生已排序的解。
这里只描述2路归并排序
左图为分解过程,右图为解决(排序)和合并过程。归并排序算法的关键操作是“合并”步骤中两个已排序序列的合并。
当待排序的序列长度为1时,递归开始“回升”(如下图),此时不需要做任何操作,因为长度为1的每个序列都已排好序(不需要排序)。
void MergeSort(int arr[],int n)//将方法封装起来{ int *tmp_array; tmp_array = (int *)malloc(n * sizeof(int)); if (tmp_array != NULL) { MSort(arr, tmp_array, 0, n - 1); free(tmp_array); } }
如果对Merge的每个递归调用都声明一个临时数组,那么任一时刻可能会有logN个临时数组处于活动期,这对小内存机器是致命的。另一方面,如果Merge动态分配并释放最小量临时空间,那么由malloc占用的时间会很多。由于Merge位于MSort的最后一行,可以在MergeSort中建立该临时数组。因此在任一时刻只需要一个临时数组活动,而且可以使用该临时数组的任意部分;我们将使用和输入数组array相同的部分。这样的话,该算法的空间占用为N,N是待排序的数组元素个数。
void MSort(int SR[],int tmp_array[],int start,int end){ int mid; if(start < end) { mid = (start + end)/2;//将SR[start..end]平分为SR[start..m]和SR[m+1..end] MSort(SR,tmp_array,start,mid);//递归地将SR[start..mid]归并为有序的TR[start..mid] MSort(SR,tmp_array,mid+1,end);//递归地将SR[mid+1..end]归并为有序的TR[mid+1..end] Merge(SR,tmp_array,start,mid,end);//将SR[start..mid]和SR[mid+1..end]归并到TR[start..end] }}
//将有序的SR[start..mid]和SR[mid+1..end]归并排序为TR1[start..end]void Merge(int SR[],int TR[],int start,int mid,int end){ int i = start,j = mid + 1,k = 0; for(;i <= mid && j <= end; k++)//将SR中记录由小到大归并到TR中 { //k为目标数组的下标。从两个子序列中选出当前最下的值放入TR数组中。 if(SR[i]
上述图解可体现Merge()过程,对两个有序的子序列进行合并操作。(原图中A[0]不存储数据,这里不考虑这个问题)。Merge()过程的思想即是:对SR两个有序子序列当前的最小值做比较,找出最小值并将其放到目标数组TR中。
第一个for循环完成后,下标k++自增指向数组第二个位置,而完成赋值的子序列的数组下标亦自增指向下一位置。若某一子序列全部完成赋值,则跳出for循环,执行if操作。(这时另一有序序列的当前所有值皆大于目标数组TR当前的最大值,直接拷贝即可。)
总体来说,递归归并排序的执行顺序可类比于二叉树的后序遍历,先一直向左下层分解,直到左下层末端为有序(即1个元素),然后合并(由2个元素组成的有序序列),接着分解同一层级右端序列直至有序,然后合并右端为有序,最后将左右序列作为子序列合并为有序。然后按这个规律一直向上进行迭代过程。
非递归归并排序
非递归的迭代方式是从最小的序列开始归并并直至完成。不需要先拆分递归,再归并退出递归。
void MergeSort2(int arr[],int n){ int* TR = (int* )malloc(n * sizeof(int)); int k = 1; while(k < n) { //交替存储合并结果,每一轮循环执行两次交换,确保目标数组存放正确的值 MergePass(arr,TR,k,n); k *= 2;//体现归并算法两两配对合并的思想 MergePass(TR,arr,k,n); k *= 2; } free(TR); //释放内存}
void MergePass(int SR[],int TR[],int s,int n){ int i = 0,j = 0; while(i <= (n-2*s))//当前元素个数确保大于等于当前步进2倍,则可合并 { Merge(SR,TR,i,i+s-1,i+2*s-1);//按当前步进合并 i = i + 2*s; } if(i<(n-s))//存在刚好剩最后两个序列的情况 Merge(SR,TR,i,i+s-1,n-1);//两两归并 else//单个序列 for(j = i;j < n;j++)//直接添加到末尾 TR[j] = SR[j];}
void Merge(int SR[],int TR[],int start,int mid,int end){ int i = start,j = mid + 1; //int k = 0; int k = i; //由于非递归直接对指定位置进行操作,故k的值为当前合并值的起始下标 for(;i <= mid && j <= end; k++)//将SR中记录由小到大归并到TR中 { //k为目标数组的下标。从两个子序列中选出当前最下的值放入TR数组中。 if(SR[i]
时间复杂度为O(nlogn)。
借鉴博客
参考书籍:《算法导论》《大话数据结构》