《大话数据结构》之归并排序

小咪咪 2022-08-20 12:10 228阅读 0赞

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define MAX_LEN 256
    typedef struct
    {
    	int iInput[MAX_LEN];
    	int iLength;
    }SqArr;
    
    int Output(SqArr *pSqToPrint)
    {
    	int iLoop;
    	for(iLoop=1;iLoop<=pSqToPrint->iLength;iLoop++)
    	{
    		printf("%d ",pSqToPrint->iInput[iLoop]);
    	}
    	printf("\n");
    	return 0;
    }
    
    void Merge(int iInputArr[],int iOutputArr[],int iStart,int iMid,int iEnd)
    {
    	int iIndex,iFirArr,iSecArr;
    
    	iIndex = iStart;
    	
    	for(iFirArr=iStart,iSecArr=iMid+1;iFirArr<=iMid && iSecArr<=iEnd;iIndex++)
    	{
    		if(iInputArr[iFirArr]>iInputArr[iSecArr])
    		{
    			iOutputArr[iIndex] = iInputArr[iSecArr];
    			iSecArr = iSecArr + 1;
    		}
    		else
    		{
    			iOutputArr[iIndex] = iInputArr[iFirArr];
    			iFirArr = iFirArr + 1;
    		}
    	}
    
    	if(iFirArr <= iMid)
    	{
    		for(;iFirArr<=iMid;iFirArr++,iIndex++)
    		{
    			iOutputArr[iIndex] = iInputArr[iFirArr];
    		}
    	}
    
    	if(iSecArr <= iEnd)
    	{
    		for(;iSecArr<=iEnd;iSecArr++,iIndex++)
    		{
    			iOutputArr[iIndex] = iInputArr[iSecArr];
    		}
    	}
    }
    
    void MSort(int iInputArr[],int iOutputArr[],int iStart,int iEnd)
    {	
    	int iMid = 0;
    	/*
    	这个数组起一个临时变量的作用，此处有很大的空间浪费
    	*/
    	int iMsort[MAX_LEN]={0};
    	
    	/*
    	实际完成的是一次数据的转存工作
    	*/
    	if(iStart == iEnd)
    	{
    		iOutputArr[iStart] = iInputArr[iEnd];
    	}
    	else
    	{
    		iMid = (iStart + iEnd)/2;
    		MSort(iInputArr,iMsort,iStart,iMid);
    		MSort(iInputArr,iMsort,iMid+1,iEnd);
    		/*
    		除第一调用MSort外，其余的iOutputArr指向的是调用者的iMsort，第一个参数iMsort则是被调用者的
    		意在将一个已经局部有序的序列传输给递归的上一层
    		*/
    		Merge(iMsort,iOutputArr,iStart,iMid,iEnd);
    	}
    }
    
    void PreMerge(int iArrInput[],int iArrOutput[],int iLength,int iStep)
    {
    	int iIndex = 1;
    	
    	/*
    	每iStep个数据互相归并
    	此处循环退出的条件是要保证（iIndex+iStep*2-1）不越界，即剩余待归并的数据要大于等于iStep*2个
    	*/
    	while(iIndex<=iLength-iStep*2+1)
    	{
    		Merge(iArrInput,iArrOutput,iIndex,iIndex+iStep-1,iIndex+iStep*2-1);
    		iIndex = iIndex + iStep*2;
    	}
    	/*
    	如果剩余未归并的数据小于iStep*2个，大于iStep个，则任然需要再归并一次
    	*/
    	if(iIndex<=iLength-iStep)
    	{
    		Merge(iArrInput,iArrOutput,iIndex,iIndex+iStep-1,iLength);
    	}
    	else
    	{
    		/*
    		如果还有剩余数据未归并，则接到输出数组最后
    		不存在没有进行归并，直接走到这行的情况
    		如果iStep<iLength则一定会产生归并；
    		如果iStep>iLength则没有必要再归并，本身已经是一个处理后的数据
    		*/
    		for(;iIndex<=iLength;iIndex++)
    		{
    			iArrOutput[iIndex] = iArrInput[iIndex];
    		}
    	}
    }
    
    void MergeSort(SqArr *pSqToSort)
    {
    	MSort(pSqToSort->iInput,pSqToSort->iInput,1,pSqToSort->iLength);
    }
    
    void MergeSort_L2(SqArr *pSqToSort)
    {
    	int iStep;
    	int iArrTemp[MAX_LEN] = {0};
    
    	iStep = 1;
    	while(iStep<=pSqToSort->iLength)
    	{
    		PreMerge(pSqToSort->iInput,iArrTemp,pSqToSort->iLength,iStep);
    		iStep = iStep * 2;
    		PreMerge(iArrTemp,pSqToSort->iInput,pSqToSort->iLength,iStep);
    		iStep = iStep * 2;
    	}
    }
    
    int main()
    {
    	char strInput[MAX_LEN];
    	char *pStrInput = NULL;
    	char *pStrtok = NULL;
    	int iLoop;
    	SqArr iToSort;
    
    	memset(strInput,0x00,sizeof(strInput));
    	memset(&iToSort,0x00,sizeof(SqArr));
    
    	printf("%s","请输入待排序数据，以逗号分隔，以回车结束：\n");
    	scanf("%s",&strInput);
    	pStrInput = strInput;
    
    	for(iLoop=1;;iLoop++,pStrInput=NULL)
    	{
    		pStrtok = strtok(pStrInput,",\n");
    		if(NULL == pStrtok)
    		{
    			break;	
    		}
    		iToSort.iInput[iLoop] = atoi(pStrtok);
    		iToSort.iLength = iLoop;
    	}
    	
    	MergeSort_L2(&iToSort);
    	Output(&iToSort);
    
    	getchar();
    	return 0;
    }

这两种归并排序的方法：

第一种，用了递归，在递归中临时转存的那个数组，有很大的空间浪费；

第二种，只定义了一个临时数组转存，用两个循环完成了一次归并，并不断循环，增加步长，直至最后完成。

某种感觉上，觉得归并和希尔很像：

归并是对相邻的数据，步长从一开始，每次翻番增长，实现排序；

希尔排序则是每间隔n个数据进行排序，间隔在不断的减少，直至最后减为一。