sort.cpp

对结构体数据或单向链表快速排序,只为了练习,不是很合理.希望对初学者有点帮助.

#include "sort.h"
#include <time.h>
#include <iostream>

using namespace std;


CSort::CSort()
{
  pOutHeader = NULL;
  pAddr = 0;
  iAddrCnt = 0;
  iTypeSize = 0;
  iNextSize = 0;
  iSegmentSize = 0;
  iNextOffset = 0;
  iCount = 0;
  iSortContent = 0;
  return;
}

CSort::~CSort()
{
  FreeSegment();
  pOutHeader = NULL;
  pAddr = 0;
  iAddrCnt = 0;
  iTypeSize = 0;
  iNextSize = 0;
  iSegmentSize = 0;
  iNextOffset = 0;
  iCount = 0;
  iSortContent = 0;
  return;
}

void CSort::Initialization(void *const pArray, int iTSize, int iACount)
{
  pOutHeader = pArray;      /* 外部数组头地址 */
  iTypeSize = iTSize;       /* 数据元素大小 */
  iCount = iACount;         /* 数组元素总个数 */
  iSegmentSize = 16;        /* 每段内存的元素个数默认为 16 */
  iSortContent = 0;         /* 数组 */
  memset(KeyOrder, 0, sizeof(KeyOrder));
  return;
}

void CSort::Initialization(void *const pArray, int iTSize, void **ppNextAddr)
{
  pOutHeader = pArray;      /* 外部数组头地址 */
  iTypeSize = iTSize;       /* 数据元素大小 */
  iCount = 0;               /* 数组元素总个数 */
  iNextOffset = (int)((long)ppNextAddr - (long)pArray); /* pNext的偏移地址 */
  iNextSize = sizeof(void*);
  iSegmentSize = 16;        /* 每段内存的元素个数默认为 16 */
  iSortContent = 1;         /* 链表 */
  memset(KeyOrder, 0, sizeof(KeyOrder));
  FreeSegment();
  return;
}

/* 交换成功返回 1, 否则返回 0 */
int CSort::DoSwap(void *p1, void *p2)
{
  void *pTemp = (void*)malloc(iTypeSize);
  if(pTemp != NULL)
  {
    memcpy(pTemp, p1, iTypeSize);
    memcpy(p1, p2, iTypeSize);
    memcpy(p2, pTemp, iTypeSize);
    free(pTemp);
    return 1;
  }
  else
  {
    printf("Error: malloc is error\n");
    return 0;
  }
}

inline int CSort::DoCopy(void *p1, void *p2)
{
  memcpy(p1, p2, iTypeSize);
  return 1;
}

inline int CSort::DoComp(char *p1, char *p2)
{
  return strcmp(p1, p2);
}

inline void* CSort::get(int iOffset)
{
  if(iSortContent == 0)
    return (void*)((long)pOutHeader + (long)(iOffset * iTypeSize));
  else
    return getlink(iOffset);
}

inline char* CSort::key_str(void *pCur, int iOrder)
{
  return (char*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

inline long* CSort::key_int(void *pCur, int iOrder)
{
  return (long*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

inline double* CSort::key_dbl(void *pCur, int iOrder)
{
  return (double*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

inline void** CSort::getnext(void* pCur)
{
  return (void**)((long)pCur + iNextOffset);
}

int CSort::GetSorted()
{
  clock_t t1, t2;
  Reset();
  t1 = clock();
  if(iSortContent == 0)
    Sorting(0, iCount - 1);
  else
  {
    LinkToBuffer();
    Sorting(0, iCount - 1);
    BufferToLink();
  }
  t2 = clock();
  iCostTime = (double)((t2 - t1)/(clock_t)1000); /* 换算成毫秒为单位 */
  return iCount;
}

void CSort::Sorting(int p, int r)
{
  int j = 0;

  if(p < r)
  {
    j = Partition(p, r);
    if(j == -1)
    {
      cout << "Error: return -1" << endl;
      return;
    }
    Sorting(p, j - 1);
    Sorting(j + 1, r);
  }
}

int CSort::Partition(int p, int r)
{
  int i = p;
  int j = r + 1;
  void *temp = (void*)malloc(iTypeSize);
  
  if(temp == NULL)
  {
    cout << "Error: Partition malloc false" << endl;
    return -1;
  }
  
  DoCopy(temp, get(p));

  if( p < r)
  {
    while(1)
    {
      while(Compare(get(++i), temp) < 0 && i <= r);
      while(Compare(get(--j), temp) > 0 && j >= p);
      
      if(i >= j) break;
      DoSwap(get(i), get(j));
    }
    DoCopy(get(p), get(j));
    DoCopy(get(j), temp);
  }
  free(temp);
  //cout << "--location--a[" << j << "]="  << endl;

  return j;
}

void CSort::Reset()
{
  FreeSegment();
  pAddr = 0;
  iAddrCnt = 0;
  if(iSortContent != 0)
    iCount = 0;
}

/************************************************************************  
 * 函  数: 初始化函数 Compare()
 * 说  明: 根据关键字数组中的方式来比较p1和p2的大小, 返回比较结果(p1 - p2)
 *         保证排序关键字数组KeyOrder[]的设置正确.
 * 参  数: 两个待比较结构体头指针
 * 返  回: > 0   升序 p1 > p2    降序 p1 < p2
 *         = 0   p1 == p2
 *         < 0   升序 p1 < p2    降序 p1 > p2
 ***********************************************************************/
inline long CSort::Compare(void *p1, void *p2)
{
  int i = 0;
  long lRet = 0;
  double db = 0.0;
  while(1)
  {
    /* 在以后分支情况中只要不满足条件就用break跳出, 返回 lResult = 0 */
    if((KeyOrder + i)->iUse == 1)
    {
      if((KeyOrder + i)->iIsChar > 0)
      { /* 字符型 */
        lRet = DoComp(key_str(p1, i), key_str(p2, i)) * (KeyOrder + i)->iSortType;
        if(lRet == 0)
          i++;
        else
          break;
      }
      else if((KeyOrder + i)->iIsChar == 0)
      { /* 整型或浮点型 */
        lRet = (*(key_int(p1, i)) - *(key_int(p2, i))) * (KeyOrder + i)->iSortType;
        if(lRet == 0)
          i++;
        else
          break;
      }
      else
      { /* 双精度型 */
        db = (*(key_dbl(p1, i)) - *(key_dbl(p2, i))) * (KeyOrder + i)->iSortType;
        if(db == 0.0)
          i++;
        else
        {
          if(db > 0)
            lRet = 1;
          else
            lRet = -1;
          break;
        }
      }
    }
    else
      break;
  }
  return lRet;
}

int CSort::SetSortKey(int iOrder, int iSortType, void *const pArray,
                      void *const pKey, int iKSize, int iUse)
{
  KeyOrder[iOrder].iKeyOffset = (int)((long)pKey - (long)pArray);
  KeyOrder[iOrder].iKeySize = iKSize;
    if(iKSize == 0)
    KeyOrder[iOrder].iIsChar = 0;  /* 整型或浮点型 */
  else if(iKSize > 0)
    KeyOrder[iOrder].iIsChar = 1;  /* 字符型 */
  else
    KeyOrder[iOrder].iIsChar = -1; /* 双精度型 */
  KeyOrder[iOrder].iUse = iUse;
  KeyOrder[iOrder].iSortType = iSortType;
  return iOrder;
}

int CSort::ExtendSegment(void)
{
  PAddr pTemp = NULL;
  pTemp = (PAddr)malloc((iAddrCnt + 1) * sizeof(TAddr));
  if(pTemp != NULL)
  {
    if(pAddr != NULL)
    {
      memcpy(pTemp, pAddr, iAddrCnt * sizeof(TAddr));
      free(pAddr);
    }
    pAddr = pTemp;
    pTemp = NULL;
    void *p = (void*)malloc(iSegmentSize * iTypeSize);
    if(p != NULL)
      pAddr[iAddrCnt].pSegAddr = p;
    else
    {
      cout << "Error: malloc is false in ExtendSegment" << endl;
      exit(1);
    }
    iAddrCnt++;
    return 0;
  }
  else
  {
    cout << "Error: malloc() is false in ExtendSegment" << endl;
    exit(1);
  }
}

void CSort::FreeSegment(void)
{
  for(int i = 0; i < iAddrCnt; i++)
    free(pAddr[i].pSegAddr);
  
  free(pAddr);
  return;
}

inline void* CSort::getlink(int iOffset)
{
  int iAddr, iIndex;
  iAddr = (int)(iOffset / iSegmentSize);
  iIndex = (int)(iOffset % iSegmentSize);
  return (void*)((long)(pAddr[iAddr].pSegAddr) + iIndex * iTypeSize);
}

void CSort::LinkToBuffer()
{
  void *pPre = NULL;
  void *pCur = pOutHeader;
  
  void **ppTemp = NULL;
  
  if(pCur == NULL)
    return;
  
  /* 第一个元素特殊处理, 不释放, 返回时保持一样 */
  if(iCount >= iSegmentSize * iAddrCnt)
  {
    ExtendSegment();
  }
  
  memcpy(getlink(iCount), pCur, iTypeSize);
  pPre = pCur;
  
  while(1)
  {
    iCount++;
	  pCur = *getnext(pCur);
	  
    if(iCount >= iSegmentSize * iAddrCnt)
      ExtendSegment();
    
    if(pCur == NULL)
      break;
    
    memcpy(getlink(iCount), pCur, iTypeSize);
    pPre = pCur;
  }
  return;
}

void CSort::BufferToLink()
{
  void* pCur = pOutHeader;

  if(iCount <= 0)
    return;
  
  for(int i = 0; i < iCount; i++)
  {
    /* 先把pNext赋给动态值 */
    memcpy(getnext(getlink(i)), getnext(pCur), iNextSize);
    memcpy(pCur, getlink(i), (iTypeSize));
    pCur = *getnext(pCur);
  }
  return;
}

void CSort::PrintInfo(void)
{
  int i = 0;
  char type[10] = "ASC";
  char content[10] = "Array";
  
  
  if(iSortContent != 0)
    sprintf(content, "Link");
  printf("The Private Information\n");
  printf("*******************************************\n");
  printf("* count of unit                : %d\n", iCount);
  printf("* count of segment             : %d\n", iAddrCnt);
  printf("* size of segment              : %d\n", iSegmentSize);
  printf("* address from outer           : 0x%x\n", pOutHeader);
  printf("* address of segment's header  : 0x%x\n", pAddr);
  while(KeyOrder[i].iUse !=0)
  {
    if(KeyOrder[i].iSortType > 0)
      sprintf(type, "ASC");
    else
      sprintf(type, "DESC");
    i++;
    printf("* Key[%d]'s sort type           : %s\n", i, type);
  }
  printf("* sort conetent(array or link) : %s\n", content);
  printf("* cost time (s)                : %0.02fs\n", iCostTime/1000);
  printf("*******************************************\n");
}