testsort.cpp

快速排序源代码

// testsort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string.h>

#define CUTOFF 8

static void shortsort(char *lo, char *hi, unsigned width, int (*comp)(const void *, const void *));
static void swap(char *p, char *q, unsigned int width);

void qsort(void *base, unsigned num, unsigned width, int (*comp)(const void *, const void *))
{
  char *lo, *hi;
  char *mid;
  char *loguy, *higuy;
  unsigned size;
  char *lostk[30], *histk[30];
  int stkptr;

  if (num < 2 || width == 0) return;
  stkptr = 0;

  lo = (char*)base;
  hi = (char *) base + width * (num - 1);

recurse:
  size = (hi - lo) / width + 1;

  if (size <= CUTOFF) 
  {
    shortsort(lo, hi, width, comp);
  }
  else 
  {
    mid = lo + (size / 2) * width;
    swap(mid, lo, width);

    loguy = lo;
    higuy = hi + width;

    for (;;) 
    {
      do { loguy += width; } while (loguy <= hi && comp(loguy, lo) <= 0);
      do { higuy -= width; } while (higuy > lo && comp(higuy, lo) >= 0);
      if (higuy < loguy) break;
      swap(loguy, higuy, width);
    }

    swap(lo, higuy, width);

    if (higuy - 1 - lo >= hi - loguy) 
    {
      if (lo + width < higuy) 
      {
        lostk[stkptr] = lo;
        histk[stkptr] = higuy - width;
        ++stkptr;
      }

      if (loguy < hi) 
      {
        lo = loguy;
        goto recurse;
      }
    }
    else
    {
      if (loguy < hi) 
      {
        lostk[stkptr] = loguy;
        histk[stkptr] = hi;
        ++stkptr;
      }

      if (lo + width < higuy) 
      {
        hi = higuy - width;
        goto recurse;
      }
    }
  }

  --stkptr;
  if (stkptr >= 0) 
  {
    lo = lostk[stkptr];
    hi = histk[stkptr];
    goto recurse;
  }
  else
    return;
}

static void shortsort(char *lo, char *hi, unsigned width, int (*comp)(const void *, const void *))
{
  char *p, *max;

  while (hi > lo) 
  {
    max = lo;
    for (p = lo+width; p <= hi; p += width) if (comp(p, max) > 0) max = p;
    swap(max, hi, width);
    hi -= width;
  }
}

static void swap(char *a, char *b, unsigned width)
{
  char tmp;

  if (a != b)
  {
    while (width--) 
    {
      tmp = *a;
      *a++ = *b;
      *b++ = tmp;
    }
  }
}

/*
int CompStr(const void* str1, const void* str2)
{
	return stricmp((char*)str1, (char*)str2);
}

char StrList[3][4] = {"dbc","bbc","abc"};

int main(int argc, char* argv[])
{
	qsort(StrList, 3, 4, CompStr);

	printf("Hello World!\n");
	return 0;
}
*/
/*
int CompNum(const void* n1, const void* n2)
{
	int nN1 = *((int*)n1);
	int nN2 = *((int*)n2);
	
	return nN1 - nN2;
}

int IntList[3] = {8, 5, 6};

int main(int argc, char* argv[])
{
	qsort(IntList, 3, 4, CompNum);

	printf("Hello World!\n");
	return 0;
}
*/


int CompStr(const void* str1, const void* str2)
{
	//return stricmp((char*)str1[0], (char*)str2);

	char **pStr1 = (char**)(str1);
	char **pStr2 = (char**)(str2);
	if (*pStr1 == NULL)
		return 1;
	else if (*pStr2 == NULL)
		return -1;
	return stricmp(*pStr1, *pStr2);
}

char *StrList[4];
char *s1 = "dbc";
char *s2 = "abc";
char *s3 = NULL;
char *s4 = "fbc";

unsigned int nLsl = 0x7908;

int main(int argc, char* argv[])
{
	StrList[0] = s1;
	StrList[1] = s2;
	StrList[2] = s4;
	StrList[3] = s3;
	qsort(StrList, 4, 4, CompStr);

	nLsl = nLsl << 27;

	printf("Hello World!\n");
	return 0;
}