归并排序——迭代实现

背景：在严蔚敏老师的那本的数据结构的书中，只给出了归并排序的递归实现代码，且注释说：递归形式的算法在形式上较简洁，但实用性差。因此这里参考小甲鱼数据结构教学视频中的代码，进行归并排序迭代实现方式的分析和理解。（小甲鱼的视频基本参考《大话数据结构》）

算法理解：

归并排序的递归方式很好理解（见严蔚敏数据结构教材即可），递归即直接假设结果已经达成，直接实现最后一步。在归并排序中就是直接写：

m = (s+t)/2;

MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
           

直接对前后两段进行归并排序，然后将前后两段归并合成，即完成排序。

代码在实际运行过程中，是在递归逐渐深入的过程中，步长每次 /2 ，然后逐层返回，完成排序。

而迭代的过程和递归正好相反，不像递归一样假设排序完成直接用最后一步开始，而是从步长 = 1（即实际意义上的第一步）开始迭代。

实际代码：（详细注释）

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 10
 
void MergeSort(int k[],int n)
{
    /* next是用来标志temp数组下标的 */
	int i,next；

    /* 每次归并都是对两段数据进行对比排序 */
    /* left\right分别代表左面和右面(前面和后面)的两段数据 */
    /* min和max分别代表各段数据的最前和最后下标 */
    int left_min,left_max,right_min,right_max;
	
    /* 申请一段内存用于存放排序的临时变量 */
	int *temp = (int *)malloc(n * sizeof(int));

	/* 步长：i；从步长=1开始逐级递增 */
	for(i=1; i<n; i*=2)
	{
		/* 每次步长递增，都从头开始归并处理 */
		for(left_min=0; left_min<n-i; left_min = right_max)
		{
                        /* 两段数据和步长之间关系 */
			right_min = left_max = left_min + i;
			right_max = left_max + i;

			/* 最后的下标不能超过n,否则无意义 */
			if(right_max>n)
			{
				right_max = n;
			}

			/* 每次的内层循环都会将排列好的数据返回到K数组,因此next指针需每次清零 */
			next = 0;

			/* 两端数据均未排完 */
			while(left_min<left_max&&right_min<right_max)
			{
				if(k[left_min] < k[right_min])
				{
					temp[next++] = k[left_min++];
					
				}
				else
				{
					temp[next++] = k[right_min++];
				}
			}

                        /* 上面的归并排序循环结束后,可能有一段数据尚未完全被排列带temp数组中 */
                        /* 剩下未排列到temp中的数据一定是按照升序排列的最大的一部分数据 */
                        /* 此时有两种情况:left未排列完成,right未排列完成
                        /* 若是left未排列完成(left_min<left_max),则对于这一段数据省去temp数组的中转,直接赋值到k数组,即从right_max开始倒着赋值 */
			/* 若是right未排列完成,则可以想到,那一段数据本就在应该放置的位置,则无需处理 */
			
			while(left_min < left_max)
			{
                                /* 上面分析应该从right_max开始倒着赋值,但是实际因为右边的数据段已经全部排列,故此时right_min=right_max */
                                /* 且这里将right_min移动到需要的位置,方便下面赋值时使用 */
				k[--right_min] = k[--left_max];	
			}

			while(next>0)
			{
				/* 把排列好的数据段赋值给k数组 */
                                /* 这里可以直接用上面经过--right_min倒数过来的right_min值 */
                                /* 经过上面倒数的处理,right_min恰好在需要赋值和不需要赋值的数据段的分界处 */
				k[--right_min] = temp[--next];		
			}
		}
	}
}
 
int main()
{
	int i,a[10] = {5,2,6,0,3,9,1,7,4,8};
	
	MergeSort(a,10);
	
	printf("排序后的结果是:");
	for(i=0; i<10; i++)
	{
		printf("%d",a[i]);
	}
	
	printf("\n\n");
	
	return 0;
	
}
           

——cloud over sky

 ——2020/3/16