qsort7.c

自己做的常用库和实现的数据结构。public domain.

void   QuickSortWithStack(   int*   pSrcArray,   int   iStart,   int   iEnd)  
  {  
  int*   pStackArray   =   new   int[80];  
  int   iLastPosition   =   0;  
  pStackArray[iLastPosition]   =   iStart;  
  pStackArray[iLastPosition   +   1]   =   iEnd;  
  iLastPosition   +=   2;  
   
  int   iMaxStackSize   =   0;  
  while   (iLastPosition   !=   0)  
  {  
  int   iEndParation   =   pStackArray[iLastPosition   -   1];  
  int   iStartParation   =   pStackArray[iLastPosition   -   2];  
  iLastPosition   -=   2;  
   
                                    //   下面用于小文件优化处理，在执行完该函数后，再调用插入排序，能提高性能  
  if   (   iEndParation   <=   iStartParation   +   32)  
  {  
  continue;  
  }  
   
  int   iBegin   =   iStartParation   -   1;  
  int   iLast   =   iEndParation;  
  int   iParationValue   =   pSrcArray[   iEndParation];  
   
  //   Paration   one   value  
  while   (1)  
  {  
  while   (pSrcArray[   ++iBegin]   <   iParationValue);  
  while   ((pSrcArray[   --iLast]   >=   iParationValue))   if   (iLast   ==   iStartParation)   break;  
   
  if   (iLast   <=   iBegin)  
  {  
  break;  
  }  
  else  
  {  
  Exchange(pSrcArray,   iBegin,   iLast);  
  }  
  }  
   
  Exchange(pSrcArray,   iBegin,   iEndParation);  
   
  if   (iBegin   >=   (iStartParation   +   iEndParation)   /   2)  
  {  
  pStackArray[iLastPosition]   =   iStartParation;  
  pStackArray[iLastPosition   +   1]   =   iBegin   -   1;  
  pStackArray[iLastPosition   +   2]   =   iBegin   +   1;  
  pStackArray[iLastPosition   +   3]   =   iEndParation;  
  }  
  else  
  {  
  pStackArray[iLastPosition]   =   iBegin   +   1;  
  pStackArray[iLastPosition   +   1]   =   iEndParation;  
  pStackArray[iLastPosition   +   2]   =   iStartParation;  
  pStackArray[iLastPosition   +   3]   =   iBegin   -   1;  
  }  
  iLastPosition   +=   4;  
  }  
   
  delete[]   pStackArray;