《大话数据结构》之快速排序

今天药忘吃喽~ 2022-08-20 12:18 198阅读 0赞

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define MAX_LEN 256
    typedef struct
    {
    	int iInput[MAX_LEN];
    	int iLength;
    }SqArr;
    
    void swap(SqArr *pToSwap,int iFirst,int iSecond)
    {
    	if (iFirst != iSecond)
    	{
    		pToSwap->iInput[iFirst] = pToSwap->iInput[iFirst] + pToSwap->iInput[iSecond];
    		pToSwap->iInput[iSecond] = pToSwap->iInput[iFirst] - pToSwap->iInput[iSecond];
    		pToSwap->iInput[iFirst] = pToSwap->iInput[iFirst] - pToSwap->iInput[iSecond];
    	}
    }
    
    int Output(SqArr *pSqToPrint)
    {
    	int iLoop;
    	for(iLoop=1;iLoop<=pSqToPrint->iLength;iLoop++)
    	{
    		printf("%d ",pSqToPrint->iInput[iLoop]);
    	}
    	printf("\n");
    	return 0;
    }
    
    /*
    此种写法有很大的缺陷，
    选low值最为基值，必须先移动high指针，
    选high值为基值，必须先移动low指针
    */
    int Partion(SqArr *pSqArrToSort,int iLow,int iHigh)
    {
    	int iKey = 0;
    	iKey = pSqArrToSort->iInput[iLow];
    	while(iLow < iHigh)
    	{
    		while(iLow<iHigh && pSqArrToSort->iInput[iHigh]>=iKey)
    		{
    			iHigh = iHigh - 1;
    		}
    		swap(pSqArrToSort,iLow,iHigh);
    
    		while(iLow<iHigh && pSqArrToSort->iInput[iLow]<=iKey)
    		{
    			iLow = iLow + 1;
    		}
    		swap(pSqArrToSort,iLow,iHigh);
    	}
    	return iLow;
    }
    
    /*
    这个写法也有局限性
    如果选择low值为key值，需要做出改动
    */
    int Partion_L2(SqArr *pSqArrToSort,int iLow,int iHigh)
    {
    	int iIndex = iLow - 1;
    	int iLoop = iLow;
    	int iKey = pSqArrToSort->iInput[iHigh];
    	for(;iLoop<iHigh;iLoop++)
    	{
    		if(pSqArrToSort->iInput[iLoop]<iKey)
    		{
    			iIndex = iIndex + 1;
    			swap(pSqArrToSort,iLoop,iIndex);
    		}
    	}
    	swap(pSqArrToSort,iIndex+1,iHigh);
    	return iIndex + 1;
    }
    
    void QuickSort(SqArr *pSqArrToSort,int low,int high)
    {
    	int iPivot;
    	if(low < high)
    	{
    		iPivot = Partion_L2(pSqArrToSort,low,high);
    		QuickSort(pSqArrToSort,low,iPivot-1);
    		QuickSort(pSqArrToSort,iPivot+1,high);
    	}
    }
    
    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;
    	}
    	
    	QuickSort(&iToSort,1,iToSort.iLength);
    	Output(&iToSort);
    
    	//getchar();
    	system("PAUSE");
    	return 0;
    }

int Partion\_L2(SqArr \*pSqArrToSort,int iLow,int iHigh)

这个函数的思想，取自《算法导论》第三版

这个函数也是有缺陷的：如果选择low值为key值，当前的代码是不适用的，需要调整。

int Partion(SqArr \*pSqArrToSort,int iLow,int iHigh)

这个划分的方式也有缺陷：

选low值最为基值，必须先移动high指针  
选high值为基值，必须先移动low指针