빠른 정렬 알고리즘 귀속과 비귀속 실현

/********************************

 *  

 * 

 *********************************/



#include <stdio.h>



/******************************

 *  

 * pList     

 * nLow      

 * nHigh     

 *****************************/

int Partiton(int *pList,int nLow,int nHigh)

{

    int nTmp = pList[nLow];

    

    while(nLow < nHigh)

    {

        while(nLow < nHigh && nTmp <= pList[nHigh])

        {

            nHigh--;

        }

        pList[nLow] = pList[nHigh];

        while(nLow < nHigh && nTmp >= pList[nLow])

        {

            nLow++;

        }

        pList[nHigh] = pList[nLow];

    }

    pList[nLow] = nTmp;

    

    return nLow;

}

/**************************

 *  Partition 

 * 

 *  

 **************************/

void QuickSort(int *pList,int nLow, int nHigh)

{

    int nPivotLoc;

    if(nLow < nHigh)

    {

        nPivotLoc = Partiton(pList, nLow, nHigh);

        QuickSort(pList, nLow, nPivotLoc - 1);

        QuickSort(pList, nPivotLoc + 1, nHigh);

    }

}



/******************************

 * 

 *  

 * 

 ******************************/

void Sort(int *pList, int nLow, int nHigh)

{

    int *pPosArr = (int *)malloc((nHigh - nLow + 1)*sizeof(int));

    int nPos = 0;

    int nTmpLow;

    int nTmpHigh;

    int nPivotLoc;

    

    pPosArr[nPos++] = nLow;

    pPosArr[nPos++] = nHigh;

    while(nPos > 0)

    {

        nTmpHigh = pPosArr[--nPos];

        nTmpLow = pPosArr[--nPos];

        if(nTmpLow >= nTmpHigh)

        {

            break;

        }

        nPivotLoc = Partiton(pList, nTmpLow, nTmpHigh);

        if(nPivotLoc - 1 > nTmpLow)

        {

            pPosArr[nPos++] = nLow;

            pPosArr[nPos++] = nPivotLoc - 1;

        }

        if(nPivotLoc + 1 < nTmpHigh)

        {

            pPosArr[nPos++] = nPivotLoc + 1;

            pPosArr[nPos++] = nHigh;

        }

    }

    free(pPosArr);

}



/******************************

 *  

 * 

 *****************************/

int main(void)

{

    int nList[] = {49, 38, 65, 97, 76, 13, 27, 49};

    int i;

    

    Sort(nList,0,sizeof(nList)/sizeof(int) - 1);

    

    for(i = 0; i < 8; i++)

    {

        printf("%d  ",nList[i]);

    }

    putchar('
');

    return 0;

}