歸并排序——疊代實作

背景：在嚴蔚敏老師的那本的資料結構的書中，隻給出了歸并排序的遞歸實作代碼，且注釋說：遞歸形式的算法在形式上較簡潔，但實用性差。是以這裡參考小甲魚資料結構教學視訊中的代碼，進行歸并排序疊代實作方式的分析和了解。（小甲魚的視訊基本參考《大話資料結構》）

算法了解：

歸并排序的遞歸方式很好了解（見嚴蔚敏資料結構教材即可），遞歸即直接假設結果已經達成，直接實作最後一步。在歸并排序中就是直接寫：

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